问题回顾
LeetCode 213 是 "打家劫舍 II"，环形房屋，不能同时偷第一个和最后一个房子。
经典解法是拆成两个子区间：
- 偷第 0 到 n-2 间房子
- 偷第 1 到 n-1 间房子
返回两者的最大值。
代码实现
以下是二维 DP 数组的写法，同时处理这两种情况：
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
const n = nums.length
if (n === 0) return 0
if (n === 1) return nums[0]
if (n === 2) return Math.max(nums[0], nums[1])
// dp[0]: 偷第一个，区间 [0..n-2]
// dp[1]: 不偷第一个，区间 [1..n-1]
const dp = Array.from({ length: 2 }, () => new Array(n).fill(0))
// 初始化 dp[0]
dp[0][0] = nums[0]
dp[0][1] = Math.max(nums[0], nums[1])
// 初始化 dp[1]
dp[1][0] = 0 // 不偷第一个房子
dp[1][1] = nums[1]
for (let i = 2; i < n; i++) {
if (i < n - 1) {
dp[0][i] = Math.max(dp[0][i - 2] + nums[i], dp[0][i - 1])
}
dp[1][i] = Math.max(dp[1][i - 2] + nums[i], dp[1][i - 1])
}
return Math.max(dp[0][n - 2], dp[1][n - 1])
}
说明
- 使用二维 dp 数组，行代表是否偷第一个房子，列代表房屋位置。
- 每行都用一维打家劫舍经典状态转移，保证互不影响。
- 最后对两个区间的结果取最大值。
总结
这个方法虽然空间复杂度比常规解法高，但思路直观，状态划分清晰，适合面试展现动态规划思考深度。你也可以尝试用滚动变量优化空间。
继续刷题，积累更多好思路！🚀