LeetCode算法笔记--打家劫舍

算法题热题HOT100 动态规划

字数统计: 382阅读时长: 1 min

 2021/01/25   Share

LeetCode算法笔记-Day64

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Example:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.


Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

方法一：动态规划

1.动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )

2.由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值  

3.举例来说：1 号房间可盗窃最大值为 33 即为 dp[1]=3，2 号房间可盗窃最大值为 44 即为 dp[2]=4，3 号房间自身的值为 22 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 55  

时间复杂度：O(n)

Answer：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length;
    if(len == 0) return 0;
    let dp = new Array(len+1);
    dp[0] = 0;
    dp[1] = nums[0];

    for(let i=2;i<len+1;i++){
        dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1])
    }
    return dp[len];
};

Next Post

LeetCode算法笔记--多数元素
Previous Post

LeetCode算法笔记--乘积最大子数组

CATALOG

1. LeetCode算法笔记-Day64
1. 1.1. 198. House Robber
2. 1.2. 方法一：动态规划
  1. 1.2.1. Answer：

