479，递归方式解打家劫舍

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

No man understands a deep book until he has seen and lived at least part of its contents.

人们只有在切身体会过某些情节后，才能理解那些深奥的书。

问题描述

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

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

示例 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

递归方式解决

这题让计算小偷偷窃的最大金额，并且不能偷窃相邻的两家，这题一看就知道，不就是前几天讲的477，动态规划解按摩师的最长预约时间吗，只不过是换汤不换药，基本原理还是一样的。这题最简单的一种解决方式就是使用动态规划，可以参照第477题，就不在过多介绍。这里来看另一种解决方式，递归。

之前讲426，什么是递归，通过这篇文章，让你彻底搞懂递归的时候提到递归的两个重要要素，一个是调用自己，一个是必须要有终止条件，我们先来定义一个函数

1private int robHelper(int[] nums, int i) {
2
3}

他表示的是前i+1（i是从0开始的，0表示的是第1个房屋）个房屋所能偷窃到的最大值，那么很明显

private int robHelper(nums, i-1)

表示的是前i个房屋所能偷窃到的最大值

private int robHelper(nums, i-2)

表示的就是前i-1个房屋所能偷窃到的最大值

因为第i-1个房屋和第i+1个房屋是不挨着的，所以如果偷完前i-1个房屋之后是可以再偷第i+1个房屋的。所以我们可以找到一种关系就是

 1private int robHelper(int[] nums, int i) {
 2    //偷上上家之前所能得到的最大值
 3    int lastLast = robHelper(nums, i - 2);
 4    //偷上家之前所能得到的最大值
 5    int last = robHelper(nums, i - 1);
 6    //偷上上家之前的还可以再偷当前这一家
 7    int cur = lastLast + nums[i];
 8    //然后返回偷当前这一家和不偷当前这一家的最大值
 9    return Math.max(last, cur);
10}

问题结束了吗，当然没有，因为我们知道递归必须要有终止条件，那么终止条件是什么呢，就是i小于0，也就是说没有房屋可偷，最终代码如下

 1public int rob(int[] nums) {
 2    return robHelper(nums, nums.length - 1);
 3}
 4
 5private int robHelper(int[] nums, int i) {
 6    //终止条件
 7    if (i < 0)
 8        return 0;
 9    //偷上上家之前所能得到的最大值
10    int lastLast = robHelper(nums, i - 2);
11    //偷上家之前所能得到的最大值
12    int last = robHelper(nums, i - 1);
13    //偷上上家之前的还可以再偷当前这一家
14    int cur = lastLast + nums[i];
15    //然后返回偷当前这一家和不偷当前这一家的最大值
16    return Math.max(last, cur);
17}

代码优化

之前讲418，剑指 Offer-斐波那契数列和356，青蛙跳台阶相关问题的时候都提到过斐波那契数列的递归计算方式，递归的时候效率是很差的，因为代码中包含大量的重复计算。这题也一样，如果非要使用递归的方式解决，可以把计算的值先存起来，下次用的时候如果有就直接去取，如果没有，再计算。

 1public int rob(int[] nums) {
 2    return robHelper(nums, nums.length - 1, new HashMap<>());
 3}
 4
 5private int robHelper(int[] nums, int i, Map<Integer, Integer> map) {
 6    //终止条件
 7    if (i < 0)
 8        return 0;
 9
10    int lastLast = 0;
11    int last = 0;
12
13    //查看map中是否存在，如果存在就从map中取，不用再计算了
14    if (map.containsKey(i - 2))
15        lastLast = map.get(i - 2);
16    else {
17        //偷上上家之前所能得到的最大值
18        lastLast = robHelper(nums, i - 2, map);
19        //如果map中不存在就计算，计算完之后要存储在map中，下次用的
20        //时候直接从map中取，不用再计算了。
21        map.put(i - 2, lastLast);
22    }
23
24    //原理同时
25    if (map.containsKey(i - 1))
26        last = map.get(i - 1);
27    else {
28        //偷上家之前所能得到的最大值
29        last = robHelper(nums, i - 1, map);
30        map.put(i - 1, last);
31    }
32
33    //偷上上家之前的还可以再偷当前这一家
34    int cur = lastLast + nums[i];
35    //然后返回偷当前这一家和不偷当前这一家的最大值
36    return Math.max(last, cur);
37}