打家劫舍 I 和 II 怎样用动态规划做？环形的情况怎么处理？

简答

打家劫舍 I（LeetCode 198）是一排房子，每间有一些钱，相邻两间不能在同一晚都偷，问最多能偷多少。比如 [2,7,9,3,1]，偷第 1、3、5 间，得到 2 + 9 + 1 = 12。

每间房只有偷和不偷两种选择。设 dp[i] 是考虑前 i 间房能偷到的最多钱：不偷第 i 间，结果就是 dp[i-1]；偷第 i 间，第 i-1 间就不能偷，结果是 dp[i-2] + nums[i]。两者取大的，就是状态转移方程。因为每一步只用到前两个值，用两个变量滚动就够了，时间 O(n)，空间 O(1)。

打家劫舍 II（LeetCode 213）把房子围成一圈，第一间和最后一间也算相邻。首尾不能同时偷，那么答案要么不含最后一间，要么不含第一间。把数组拆成这两段，每段都是一排房子，用 I 的方法各算一次，取较大的。

要注意只有一间房的情况：拆成两段后两段都是空的，结果会变成 0，所以要单独返回这一间的钱。

打家劫舍 I

prev 表示前 i-2 间的最优结果，curr 表示前 i-1 间的最优结果，每读一间房就往前滚一格。

function rob(nums) {
  let prev = 0;
  let curr = 0;
  for (const money of nums) {
    // 偷这一间就只能接 prev，不偷就沿用 curr
    const next = Math.max(curr, prev + money);
    prev = curr;
    curr = next;
  }
  return curr;
}

console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([2, 7, 9, 3, 1])); // 12
console.log(rob([2, 1, 1, 2])); // 4

[2,1,1,2] 这组容易出错。有人以为“隔一间偷一间”就行，可是偷第 1、3 间得 3，偷第 2、4 间也得 3，真正的最优是偷第 1 和第 4 间，得 4。中间可以连着跳过两间，所以不能简单地按奇偶位置选，要靠状态转移来比较。

为什么初始值都是 0？还没有房子时偷到的就是 0。第一间房进来时，Math.max(0, 0 + nums[0]) 正好等于 nums[0]，不用单独处理。动态规划的一般思路见《动态规划怎么入门？爬楼梯和最长递增子序列怎样做？》。

打家劫舍 II：房子围成一圈

function robLine(nums, start, end) {
  let prev = 0;
  let curr = 0;
  for (let i = start; i <= end; i += 1) {
    const next = Math.max(curr, prev + nums[i]);
    prev = curr;
    curr = next;
  }
  return curr;
}

function robCircle(nums) {
  if (nums.length === 1) return nums[0];
  // 首尾相邻，所以要么不偷最后一间，要么不偷第一间
  return Math.max(robLine(nums, 0, nums.length - 2), robLine(nums, 1, nums.length - 1));
}

console.log(robCircle([2, 3, 2])); // 3
console.log(robCircle([1, 2, 3, 1])); // 4
console.log(robCircle([1, 2, 3])); // 3
console.log(robCircle([5])); // 5

[2,3,2] 如果当成一排，偷第 1 和第 3 间得 4。可是围成一圈后这两间相邻，不能都偷，所以只能偷中间那间，得 3。

拆成两段为什么不会漏掉答案？任何一种合法偷法，第一间和最后一间至少有一间没偷。没偷最后一间的偷法都落在第一段里，没偷第一间的都落在第二段里，所以两段的最大值合起来覆盖了所有情况。

常见追问

如果还要输出偷了哪几间房，怎么办？

滚动变量只留下了最大值，所以要保留完整的 dp 数组，再从后往前回溯：如果 dp[i] 等于 dp[i-1]，说明第 i 间没偷，往前看一间；否则第 i 间偷了，跳到 i-2 继续。

房子排成二叉树（打家劫舍 III）怎么做？

对每个节点返回两个值：偷这个节点时的最大值和不偷时的最大值。偷当前节点，两个孩子都不能偷；不偷当前节点，每个孩子各自取偷或不偷中较大的。后序遍历一次就能算出来。