198.打家劫舍

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下一夜之内能够偷窃到的最高金额。 image.png

思路

打家劫舍是经典的动态规划思路问题，它符合以下2个特点：

  • 最优子结构：最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。
  • 无后向性：本阶段决策无需考虑之后阶段的决策

在这题里面这2个特性的体现：

最优子结构

在验证最优子结构前，需要分析一下打劫的本质。如果想要打劫k间房子，会有2种情况:

  • 如果第k间房子被打劫了， 那打劫的钱数是0 ~ k-2 间房间打劫到最多的钱 + 房子k里面的钱
  • 如果第k间房子没被打劫， 那打劫的钱数就是0 ~ k-1 房间里面打劫到最多的钱

这样可以发现，不过是哪种可能性，都会包含比k间房少的时候的打劫钱最多的方案，这就是最优子结构，当前的答案包含了前面过程的最优答案。

无后向性

在最优子结构里面我们可以看到， 最终的方案是由：

  • k-1 的最优方案
  • k-2 的最优方案

变化来的，标准只有一个，就是当前房子打劫到的钱最多。就想只有3间房子，考虑第三间房子要不要偷的时候，完全不用管有第五间房时候第三间要不要选，那是打劫第五间房的时候要考虑的事情，自己只需要根据前2间房的情况来做选择。这就是无后向性

递推公式

验证了上面两个特性，代表可以使用动态规划。其实上面两个过程，就是完成了动态规划的第一个中重要步骤：
确定子问题。现在需要根据子问题写出递推公式：
2020/10/27 - 图2
这里的n是大于1的情况。当n=0时，没有房子所以dp[0]=0，当n=1时，只有这一间可以投，所以dp[1] = nums[1]

计算顺序

有些动态规划需要根据最后的结构，推导出初始状态。而这题是需要根据根据一开始的状态，推到到最后，计算顺序是从dp[0] - dp[n]

代码

空间优化前

基于以上信息，我们就可以开始编写代码，定义一个dp数组，大小是n+1（因为要包括0）,然后给dp[0]和dp[1]附上初值，之后按照递推公式进行推导

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         if (nums.size() == 0) {
  5.             return 0;
  6.         }
  8.         int N = nums.size();
  9.         vector<int> dp(N+1, 0);
  10.         dp[0] = 0;
  11.         dp[1] = nums[0];
  13.         for (int k = 2; k <= N; k++) {
  14.             dp[k] = max(dp[k-1], nums[k-1] + dp[k-2]);
  15.         }
  16.         return dp[N];
  17.    }
  18. };

空间优化后

和昨天的题目一样，因为只需要考虑前面两天的情况，所以可以不用特意开一个数组，用两个变量就可以完成：

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.        int prev = 0;
  5.        int curr = 0;
  6.        for (int i : nums) {
  7.             int temp = max(curr, prev + i);
  8.             prev = curr;
  9.             curr = temp;
  10.         }
  11.         return curr;
  12.     }
  13. };

总结

写动态规划的题目一共有4个步骤