打家劫舍-198

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

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

示例 1：

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

示例 2：

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

提示：

• 0 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 400

思路

正月点灯笼的视频提到这个题目。

假设有序列:

index: 0    1    2    3    4    5    6
arr:   1    2    4    1    7    8    3

小偷希望逛完这七家房子，找到收益最大的值，即求 #card=math&code=OPT%286%29)，整个过程会如下图:

由于有重叠子问题，所以我们可以用动态规划来找最优解。

我们创建一个dp[]数组，里面的值代表：到当前这个屋子为止，小偷能获得的最大收益。

以我上面的序列为例：

• 假设只有1个屋子，则dp[0] = 1，即只能偷第0个屋子；
• 假设有2个屋子，则dp[1] = 2，因为arr[1] > arr[0]；
• 假设有3个屋子，则dp[2] = max( dp[2-1], arr[2]+dp[2-2] )，意思是：
  小偷有2个选择：偷 或 不偷；
  • 如果选择偷，则能得到arr[2] + dp[2-2]的价值；
  • 如果选不偷，则能得到dp[2-1]的价值；

小偷要在里面选一个最大的。

• 如果有4个屋子，则dp[3] = max( dp[3-1], arr[3] + dp[3-2] )；
• ….
• 如果有 i 个屋子，则：%20%3D%20%0A%5Cbegin%7Bcases%7D%0Aarr%5Bi%5D%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20arr%5Bi-1%5D%2C%5C%20arr%5Bi%5D%5C%20%5C%7D%2C%20%26%20i%20%3D%201%5C%5C%0Amax%5C%7B%5C%20arr%5Bi%5D%20%2B%20dp(i-2)%2C%5C%20dp(i-1)%5C%20%5C%7D%2C%20%26i%20%3E%201%0A%5Cend%7Bcases%7D%0A#card=math&code=dp%28i%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0Aarr%5Bi%5D%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20arr%5Bi-1%5D%2C%5C%20arr%5Bi%5D%5C%20%5C%7D%2C%20%26%20i%20%3D%201%5C%5C%0Amax%5C%7B%5C%20arr%5Bi%5D%20%2B%20dp%28i-2%29%2C%5C%20dp%28i-1%29%5C%20%5C%7D%2C%20%26i%20%3E%201%0A%5Cend%7Bcases%7D%0A)

有了递推公式，我们可以写代码了。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 0)   return 0;
        if(nums.size() == 1)   return nums[0];
        int* dp = new int[ nums.size() ];
        dp[0] = nums[0];
        dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        for(int i = 2; i < nums.size(); i++) {
            int take_it = nums[i] + dp[i-2];
            int no_take = dp[i-1];
            dp[i] = take_it > no_take ? take_it : no_take;
        }
        int MAX = dp[ nums.size()-1 ];
        delete[] dp;
        return MAX;
    }
};