198 打家劫舍

本文最后更新于：2021年2月22日 下午

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Solution

参考：《算法小抄》2.18 、**@liuyubobobo**

  • 备忘录方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# @lc code=start
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        memo = [-1]*n
        
        def dp(nums, start):
            if start>=n:
                return 0
            if memo[start]!=-1:
                return memo[start]
            
            res = max(dp(nums, start+1), nums[start]+dp(nums, start+2))
            memo[start]=res
            return res
        
        return dp(nums, 0)
# @lc code=end

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    vector<int> memo;

    int go(const vector<int>& nums, int index){
        if(index >= nums.size())
            return 0;
        
        if(memo[index] != -1)
            return memo[index];
        
        return memo[index] = max(go(nums, index+1), nums[index]+go(nums,index+2));
    }

public:
    int rob(vector<int>& nums) {
        memo.clear();
        memo = vector<int>(nums.size(), -1);
        return go(nums, 0);
    }
};
  • 由于 dp[i] 仅和 dp[i-1] 和 dp[i-2] 有关，进行优化
1
2
3
4
5
6
7
8
class Solution:
    def rob(self, nums: List[int]) -> int:
        cur, pre1, pre2 = 0,0,0
        for num in nums:
            cur = max(pre1, pre2+num)
            pre2 = pre1
            pre1 = cur
        return cur

动态规划

  • 利用 dp 数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// @lc code=start
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        vector<int> dp(n+1, 0);

        dp[n-1] = nums[n-1];
        for(int i=n-2; i>=0; --i){
            dp[i] = max(dp[i+1], dp[i+2]+nums[i]);
        }
        return dp[0];
    }
};
// @lc code=end