力扣第198题-打家劫舍

题目

看到题目，应该是动态规划的题，但是我不想动脑子，就直接回溯吧，估计没有错，但是超时了，代码放这里。

var rob = function(nums) {
    return Math.max(maxNum(nums,0,0),maxNum(nums,1,0));
};
function maxNum(nums,i,all){
    if(i>=nums.length)return all;
    all += nums[i];
    if(i>=nums.length-2)return all;
    let left = maxNum(nums,i+2,all);
    let right = maxNum(nums,i+3,all);
    return Math.max(left,right);
}

我又想了想，感觉这和斐波那契数列有一点像呀，然后很快我就想到了另一种方法，代码如下，通过是通过了但是击败的人有点少。这种解法也算是动态规划。

var rob = function(nums) {
    if(nums.length===1)return nums[0];
    if(nums.length===2)return Math.max(nums[0],nums[1]);
    for(let i=2;i<nums.length;i++){
        const max = Math.max(nums[i-2],nums[i-3]||0);
        nums[i] += max;
    }
    console.log(nums);
    return Math.max(nums[nums.length-1],nums[nums.length-2]);
};

另一种动态规划写法，这一种明显快了不少，就是分析偷该屋子和不偷该屋子的两种情况。

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

然后我忽然看到，LeetCode热题HOT100里面还有一道打家劫舍3，立马去写一下。