题目描述（简单难度）

198. House Robber - 图1

一个数组，每个元素代表商店的存款，一个小偷晚上去偷商店，问最多能偷多少钱。有一个前提，不能偷相邻的商店，不然警报会响起。

思路分析

一道很典型的通过子问题去解决原问题的题目，所以可以通过递归以及动态规划解决。

如果我们需要求前 n 家商店最多能偷多少钱，并且知道了前 n - 1 家店最多能偷的钱数，前 n - 2 家店最多能偷的钱数。

对于第 n 家店，我们只能选择偷或者不偷。

如果偷的话，那么前 n 家商店最多能偷的钱数就是「前 n - 2 家店最多能偷的钱数」加上「第 n 家店的钱数」。因为选择偷第 n 家商店，第 n - 1 家商店就不可以偷了。

如果不偷的话，那么前 n 家商店最多能偷的钱数就是「前 n - 1 家店最多能偷的钱数」。

最终前 n 家商店最多能偷的钱数就是上边两种情况选择较大的值。

接下来就是递归出口或者说初始条件。

当 n = 0，也就没有商店，那么能偷的最大钱数当然是 0 了。

当 n = 1，也就是只有一家店的时候，能偷的最大钱数就是当前店的钱数。

解法一 递归

通过上边的分析，代码也就直接出来了。

  1. public int rob(int[] nums) {
  2.     return robHelpler(nums, nums.length);
  3. }
  5. private int robHelpler(int[] nums, int n) {
  6.     if (n == 0) {
  7.         return 0;
  8.     }
  9.     if (n == 1) {
  10.         return nums[0];
  11.     }
  12.     return Math.max(robHelpler(nums, n - 2) + nums[n - 1], robHelpler(nums, n - 1));
  13. }

然后就会意料之中的超时。

198. House Robber - 图2

原因很简单，因为递归中会计算很多重复的解，解法方案的话我们就是把递归过程中的解存起来，第二次遇到的话直接返回即可。

  1. public int rob(int[] nums) {
  2.     int[] map = new int[nums.length + 1];
  3.     Arrays.fill(map, -1);
  4.     return robHelpler(nums, nums.length, map);
  5. }
  7. private int robHelpler(int[] nums, int n, int[] map) {
  8.     if (n == 0) {
  9.         return 0;
  10.     }
  11.     if (n == 1) {
  12.         return nums[0];
  13.     }
  14.     if (map[n] != -1) {
  15.         return map[n];
  16.     }
  17.     int res = Math.max(robHelpler(nums, n - 2, map) + nums[n - 1], robHelpler(nums, n - 1, map));
  18.     map[n] = res;
  19.     return res;
  20. }

解法二 动态规划

有了上边的递归和之前的分析，其实动态规划也可以直接出来了。

用 dp[n] 数组表示前 n 天能够带来的最大收益。

dp[n] = Math.max(dp[n - 2] + nums[n - 1], dp[n - 1] )。

初始条件的话，

dp[0] = 0 以及 dp[1] = nums[0]。

  1. public int rob(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) {
  4.         return 0;
  5.     }
  6.     if (n == 1) {
  7.         return nums[0];
  8.     }
  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.         dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
  15.     }
  16.     return dp[n];
  17. }

接下来就是动态规划空间复杂度上的优化，比如 5题，10题，53题，72题 ，115 题 等等都已经用过了。

原因就是我们更新 dp[i] 的时候，只需要 dp[i - 1] 以及 dp[i - 2] 的信息，再之前的信息就不需要了，所以我们不需要数组，只需要几个变量就可以了。

  1. public int rob(int[] nums) {
  2.     int n = nums.length;
  3.     if (n == 0) {
  4.         return 0;
  5.     }
  6.     if (n == 1) {
  7.         return nums[0];
  8.     }
  10.     int pre = 0; //代替上边代码中的 dp[i - 2]
  11.     int cur = nums[0]; //代替上边代码中的 dp[i - 1] 和 dp[i]
  12.     for (int i = 2; i <= n; i++) {
  13.         int temp = cur;
  14.         cur = Math.max(pre + nums[i - 1], cur);
  15.         pre = temp;
  16.     }
  17.     return cur;
  18. }

总

一道很典型的题，可以体会从递归 -> 递归加缓冲 -> 动态规划 -> 动态规划空间复杂度优化这一系列的过程，如果题目做的多了，最开始就可以直接想到最后的方法了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情