关于算法:动态规划之打家劫舍

读完本文，你能够去力扣拿下如下题目：

198. 打家劫舍

213. 打家劫舍 II

337. 打家劫舍 III

———–

有读者私下问我 LeetCode「打家劫舍」系列问题（英文版叫 House Robber）怎么做，我发现这一系列题目的点赞十分之高，是比拟有代表性和技巧性的动静布局题目，明天就来聊聊这道题目。

打家劫舍系列总共有三道，难度设计十分正当，层层递进。第一道是比拟规范的动静布局问题，而第二道融入了环形数组的条件，第三道更绝，把动静布局的自底向上和自顶向下解法和二叉树联合起来，我认为很有启发性。如果没做过的敌人，倡议学习一下。

上面，咱们从第一道开始剖析。

House Robber I

public int rob(int[] nums);

题目很容易了解，而且动静布局的特色很显著。咱们前文「动静布局详解」做过总结，解决动静布局问题就是找「状态」和「抉择」，仅此而已。

假想你就是这个业余匪徒，从左到右走过这一排房子，在每间房子前都有两种 抉择：抢或者不抢。

如果你抢了这间房子，那么你 必定 不能抢相邻的下一间房子了，只能从下下间房子开始做抉择。

如果你不抢这件房子，那么你能够走到下一间房子前，持续做抉择。

当你走过了最初一间房子后，你就没得抢了，能抢到的钱显然是 0（base case）。

以上的逻辑很简略吧，其实曾经明确了「状态」和「抉择」：你背后房子的索引就是状态，抢和不抢就是抉择。

在两个抉择中，每次都选更大的后果，最初失去的就是最多能抢到的 money：

// 主函数
public int rob(int[] nums) {return dp(nums, 0);
}
// 返回 nums[start..] 能抢到的最大值
private int dp(int[] nums, int start) {if (start >= nums.length) {return 0;}
    
    int res = Math.max(
            // 不抢，去下家
            dp(nums, start + 1), 
            // 抢，去下下家
            nums[start] + dp(nums, start + 2)
        );
    return res;
}

明确了状态转移，就能够发现对于同一 start 地位，是存在重叠子问题的，比方下图：

盗贼有多种抉择能够走到这个地位，如果每次到这都进入递归，岂不是浪费时间？所以说存在重叠子问题，能够用备忘录进行优化：

private int[] memo;
// 主函数
public int rob(int[] nums) {
    // 初始化备忘录
    memo = new int[nums.length];
    Arrays.fill(memo, -1);
    // 匪徒从第 0 间房子开始抢劫
    return dp(nums, 0);
}

// 返回 dp[start..] 能抢到的最大值
private int dp(int[] nums, int start) {if (start >= nums.length) {return 0;}
    // 防止反复计算
    if (memo[start] != -1) return memo[start];
    
    int res = Math.max(dp(nums, start + 1), 
                    nums[start] + dp(nums, start + 2));
    // 记入备忘录
    memo[start] = res;
    return res;
}

这就是自顶向下的动静布局解法，咱们也能够略作批改，写出 自底向上 的解法：

 int rob(int[] nums) {
    int n = nums.length;
    // dp[i] = x 示意：// 从第 i 间房子开始抢劫，最多能抢到的钱为 x
    // base case: dp[n] = 0
    int[] dp = new int[n + 2];
    for (int i = n - 1; i >= 0; i--) {dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
    }
    return dp[0];
}

咱们又发现状态转移只和 dp[i] 最近的两个状态无关，所以能够进一步优化，将空间复杂度升高到 O(1)。

int rob(int[] nums) {
    int n = nums.length;
    // 记录 dp[i+1] 和 dp[i+2]
    int dp_i_1 = 0, dp_i_2 = 0;
    // 记录 dp[i]
    int dp_i = 0; 
    for (int i = n - 1; i >= 0; i--) {dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

以上的流程，在咱们「动静布局详解」中具体解释过，置信大家都能手到擒来了。我认为很有意思的是这个问题的 follow up，须要基于咱们当初的思路做一些奇妙的应变。

House Robber II

这道题目和第一道形容根本一样，匪徒仍然不能抢劫相邻的房子，输出仍然是一个数组，然而通知你 这些房子不是一排，而是围成了一个圈。

也就是说，当初第一间房子和最初一间房子也相当于是相邻的，不能同时抢。比如说输出数组 nums=[2,3,2]，算法返回的后果应该是 3 而不是 4，因为结尾和结尾不能同时被抢。

这个约束条件看起来应该不难解决，咱们前文「枯燥栈解决 Next Greater Number」说过一种解决环形数组的计划，那么在这个问题上怎么解决呢？

首先，首尾房间不能同时被抢，那么只可能有三种不同状况：要么都不被抢；要么第一间房子被抢最初一间不抢；要么最初一间房子被抢第一间不抢。

那就简略了啊，这三种状况，那种的后果最大，就是最终答案呗！不过，其实咱们不须要比拟三种状况，只有比拟状况二和状况三就行了，因为这两种状况对于房子的抉择余地比状况一大呀，房子里的钱数都是非正数，所以抉择余地大，最优决策后果必定不会小。

所以只需对之前的解法稍作批改即可：

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), 
                    robRange(nums, 1, n - 1));
}

// 仅计算闭区间 [start,end] 的最优后果
int robRange(int[] nums, int start, int end) {
    int n = nums.length;
    int dp_i_1 = 0, dp_i_2 = 0;
    int dp_i = 0;
    for (int i = end; i >= start; i--) {dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

至此，第二问也解决了。

House Robber III

第三题又想法设法地变花色了，此匪徒发现当初面对的房子不是一排，不是一圈，而是一棵二叉树！房子在二叉树的节点上，相连的两个房子不能同时被抢劫，果然是传说中的高智商立功：

整体的思路齐全没变，还是做抢或者不抢的抉择，去收益较大的抉择。甚至咱们能够间接按这个套路写出代码：

Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {if (root == null) return 0;
    // 利用备忘录打消重叠子问题
    if (memo.containsKey(root)) 
        return memo.get(root);
    // 抢，而后去下下家
    int do_it = root.val
        + (root.left == null ? 
            0 : rob(root.left.left) + rob(root.left.right))
        + (root.right == null ? 
            0 : rob(root.right.left) + rob(root.right.right));
    // 不抢，而后去下家
    int not_do = rob(root.left) + rob(root.right);
    
    int res = Math.max(do_it, not_do);
    memo.put(root, res);
    return res;
}

这道题就解决了，工夫复杂度 O(N)，N 为数的节点数。

然而这道题让我感觉奇妙的点在于，还有更丑陋的解法。比方上面是我在评论区看到的一个解法：

int rob(TreeNode root) {int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/* 返回一个大小为 2 的数组 arr
arr[0] 示意不抢 root 的话，失去的最大钱数
arr[1] 示意抢 root 的话，失去的最大钱数 */
int[] dp(TreeNode root) {if (root == null)
        return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    // 抢，下家就不能抢了
    int rob = root.val + left[0] + right[0];
    // 不抢，下家可抢可不抢，取决于收益大小
    int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);
    
    return new int[]{not_rob, rob};
}

工夫复杂度 O(N)，空间复杂度只有递归函数堆栈所需的空间，不须要备忘录的额定空间。

你看他和咱们的思路不一样，批改了递归函数的定义，稍微批改了思路，使得逻辑自洽，仍然失去了正确的答案，而且代码更丑陋。这就是咱们前文「不同定义产生不同解法」所说过的动静布局问题的一个个性。

实际上，这个解法比咱们的解法运行工夫要快得多，尽管算法剖析层面工夫复杂度是雷同的。起因在于此解法没有应用额定的备忘录，缩小了数据操作的复杂性，所以理论运行效率会快。