题目描述

你是一名专业的打劫者，计划对一排房屋进行打劫。每个房屋都存放着一定数额的现金，但是你不能打劫相邻的房屋，因为这会引起警方的注意。现在，给定一个非负整数数组，其中每个元素代表一个房屋内存放的现金数额，你需要计算在不惊动警方的情况下，能够打劫到的最大金额是多少。

示例

输入：[1,2,3,1] 输出：4 解释：你可以选择打劫第1个房屋（金额=1）和第3个房屋（金额=3），总金额为4。

解题思路

这个问题可以使用动态规划来解决。我们定义一个数组dp，其中dp[i]表示打劫到第i个房屋时能够得到的最大金额。对于每个房屋，我们有两个选择：

1. 打劫当前房屋，那么就不能打劫前一个房屋，所以当前房屋的最大金额就是前一个房屋前两个房屋的最大金额加上当前房屋的金额，即dp[i] = dp[i-2] + nums[i]。
2. 不打劫当前房屋，那么当前房屋的最大金额就是前一个房屋的最大金额，即dp[i] = dp[i-1]。

我们取这两个选择中的较大值作为dp[i]的值。

PHP 代码示例

function rob($nums) {
    $n = count($nums);
    if ($n == 0) return 0;
    if ($n == 1) return $nums[0];
    
    $dp = array_fill(0, $n, 0);
    $dp[0] = $nums[0];
    $dp[1] = max($nums[0], $nums[1]);
    
    for ($i = 2; $i < $n; $i++) {
        $dp[$i] = max($dp[$i-1], $dp[$i-2] + $nums[$i]);
    }
    
    return $dp[$n-1];
}

// 示例用法
$nums = [1, 2, 3, 1];
echo rob($nums);  // 输出 4

Python 代码示例

def rob(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[n-1]

# 示例用法
nums = [1, 2, 3, 1]
print(rob(nums))  # 输出 4

JavaScript 代码示例

function rob(nums) {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    
    for (let i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    return dp[n-1];
}

// 示例用法
const nums = [1, 2, 3, 1];
console.log(rob(nums));  // 输出 4

// 码小课网站中有更多相关内容分享给大家学习

这些代码示例提供了对“打劫房屋”问题的解决方案，并展示了如何使用PHP、Python和JavaScript来实现这一算法。