跳到主要内容

打家劫舍

打家劫舍的状态如何定义？​

  • 问题: 相邻房屋不能同时偷, 求最高金额 (198);
  • 阶段: 按房屋顺序划分;
  • 状态: dp[i] 为前 i 间房屋能偷到的最高金额;
  • 口径: 用"前 i 间"而不是"偷第 i 间", 因为可以跳过当前房屋;

如何写出转移方程？​

  • 决策: 对第 i 间房屋只有偷与不偷两种选择;
  • 不偷: dp[i] = dp[i-1];
  • 偷: 前 i-2 间的结果加上本次金额, dp[i] = dp[i-2] + nums[i-1];
  • 方程: dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);
  • 初值: dp[0] = 0, dp[1] = nums[0];
  • 答案: dp[n];
const rob = (nums) => {
  const dp = new Array(nums.length + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  }
  return dp[nums.length];
};
  • 复杂度: 时间 O(n), 空间 O(n), 可用两个滚动变量降到 O(1);

环形排列的打家劫舍如何处理？​

  • 问题: 房屋首尾相连, 第一间和最后一间也不能同时偷 (213);
  • 拆解: 首尾不能同时选, 于是把环形拆成两个线性子问题;
  • 子问题一: 只考虑 [0, n-2] (不偷最后一间);
  • 子问题二: 只考虑 [1, n-1] (不偷第一间);
  • 答案: max(子问题一, 子问题二);
  • 特判: 只有一间房屋时直接返回该金额;
const rob2 = (nums) => {
  const helper = (arr) => {
    let prev = 0;
    let curr = 0;
    for (const x of arr) {
      [prev, curr] = [curr, Math.max(curr, prev + x)];
    }
    return curr;
  };
  if (nums.length === 1) return nums[0];
  return Math.max(helper(nums.slice(1)), helper(nums.slice(0, -1)));
};