198. 打家劫舍

题目要求：

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

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

示例 1:

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

 

解题思路：

1. 定义函数子问题，前k个房子能获得的最大金额为f(k),   当k=n时，则是n个房子获得的最大金额f(n);

2. 寻找函数关系式，f(k)  f(k-1) f(k-2) 存在的某种关系；

假设一共有 n 个房子，每个房子的金额为nums[i], 子问题 f(k)表示前k个房子能获得的最大金额。那么k个房子有两种偷法：

如图所示，两种情况中，选择金额较大的一种结果：f(k) = max{  f(k-2) + nums[k-1],  f(k-1) };

3. 找出初始值；

前0个房子， k=0， f(0) =0;   前1个房子，k=1，f(1) = nums[0] ;

 

 

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

 

题目优化：

空间优化的基本原理是，很多时候我们并不需要始终持有全部的 DP 数组。对于小偷问题，我们发现，最后一步计算 f(n)f(n) 的时候，实际上只用到了 f(n-1)f(n−1) 和 f(n-2)f(n−2) 的结果。n-3n−3 之前的子问题，实际上早就已经用不到了。那么，我们可以只用两个变量保存两个子问题的结果，就可以依次计算出所有的子问题。下面的图片比较了空间优化前和优化后的对比关系：

 

 1 int rob(vector<int>& nums) {
 2     int prev = 0;
 3     int curr = 0;
 4 
 5     // 每次循环，计算“偷到当前房子为止的最大金额”
 6     for (int i : nums) {
 7         // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
 8         // dp[k] = max{ dp[k-1], dp[k-2] + i }
 9         int temp = max(curr, prev + i);
10         prev = curr;
11         curr = temp;
12         // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
13     }
14 
15     return curr;
16 }