198. 打家劫舍

[qulingyuan]

198. 打家劫舍

解题思路

f(k)表示前k个房屋中能偷窃到的最大数额。

Ak表示第k个房屋的钱数。

f(k) = max(f(k-2) +Ak,f(k-1))

解题步骤

定义子问题：f(k) = max(f(k-2) +Ak,f(k-1))

反复执行：从2循环到n，执行上述公式。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 0) return 0;
    const dp = [0,nums[0]];
    for(let i = 2; i <= nums.length; i++ ){
        dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
    }
    return dp[nums.length];
};

可以不用数组，只用两个变量记录即可。可优化时间复杂度为O(1):

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if(nums.length === 0) return 0;
    let dp0 = 0;
    let dp1 = nums[0];
    for(let i = 2; i <= nums.length; i++ ){
        const dp2 = Math.max(dp0+nums[i-1],dp1);
        dp0 = dp1;
        dp1 = dp2;
    }
    return dp1;
};