打家劫舍

问题

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

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

解答

打家劫舍 I - 线性数组

/**
 * 基础版：线性数组
 * @param {number[]} nums - 每间房屋的金额
 * @return {number} 最高金额
 */
function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  
  // dp[i] 表示偷到第 i 间房屋时的最高金额
  // 状态转移：偷当前房 vs 不偷当前房
  let prev2 = 0;        // dp[i-2]
  let prev1 = nums[0];  // dp[i-1]
  
  for (let i = 1; i < nums.length; i++) {
    const curr = Math.max(
      prev1,              // 不偷当前房
      prev2 + nums[i]     // 偷当前房
    );
    prev2 = prev1;
    prev1 = curr;
  }
  
  return prev1;
}

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

打家劫舍 II - 环形数组

/**
 * 环形版：首尾相连
 * 思路：分两种情况，偷第一间或偷最后一间
 * @param {number[]} nums
 * @return {number}
 */
function robCircle(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.max(nums[0], nums[1]);
  
  // 辅助函数：计算区间 [start, end] 的最大金额
  const robRange = (start, end) => {
    let prev2 = 0;
    let prev1 = 0;
    
    for (let i = start; i <= end; i++) {
      const curr = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = curr;
    }
    
    return prev1;
  };
  
  // 情况1：偷第一间，不偷最后一间 [0, n-2]
  // 情况2：不偷第一间，偷最后一间 [1, n-1]
  return Math.max(
    robRange(0, nums.length - 2),
    robRange(1, nums.length - 1)
  );
}

// 测试
console.log(robCircle([2, 3, 2]));    // 3 (只偷 3)
console.log(robCircle([1, 2, 3, 1])); // 4 (偷 2 和 3 或 1 和 3)

打家劫舍 III - 二叉树

/**
 * 树形版：二叉树结构
 * 思路：树形 DP，每个节点返回 [不偷, 偷] 两种状态
 */
function TreeNode(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
function robTree(root) {
  // 返回 [不偷当前节点的最大值, 偷当前节点的最大值]
  const dfs = (node) => {
    if (!node) return [0, 0];
    
    const left = dfs(node.left);
    const right = dfs(node.right);
    
    // 不偷当前节点：子节点可偷可不偷，取最大
    const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    
    // 偷当前节点：子节点都不能偷
    const rob = node.val + left[0] + right[0];
    
    return [notRob, rob];
  };
  
  const result = dfs(root);
  return Math.max(result[0], result[1]);
}

// 构建测试树
//     3
//    / \
//   2   3
//    \   \
//     3   1
const root = new TreeNode(3);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(1);

console.log(robTree(root)); // 7 (偷 3 + 3 + 1)

关键点

• 状态定义：dp[i] 表示偷到第 i 间房屋时的最高金额
• 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，即偷或不偷当前房
• 空间优化：只需保存前两个状态，空间复杂度从 O(n) 降到 O(1)
• 环形处理：拆分为两个线性问题，分别计算 [0, n-2] 和 [1, n-1]
• 树形 DP：后序遍历，每个节点维护「偷」和「不偷」两种状态