Skip to main content

198. House Robber

分析

定义 dp[i][0] 为选择在第i家选择不偷的情况下的最大值
定义 dp[i][1] 为选择在第i家选择偷 的情况下的最大值

dp[i][0] = max(dp[i-1][1], dp[i-1][0])
dp[i][1] = dp[i-1][0] + nums[i]
dp[0][0] = 0
dp[0][1] = 0

只涉及 i - 1 的状态需要 可以状态压缩

看了别人的题解 还有另外一种思考方式

定义 dp[i] 为从从开始到第i个元素时能够获得的最大值
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

只涉及靠近当前的两个状态 一样可以压缩

似乎大多数题解都是这个逻辑,我觉得 dp[i-1] 和 当前选择之间的关系在这个递推关系中没有第一个方法看着清晰, dp[i-1] 和 当前 num 的选与不选感觉是存在可能的

题解

function rob(nums: number[]): number {
let preNoRub = 0, preRub = 0

for (let i = 0; i < nums.length; i++) {
const tempPreNoRub = preNoRub
preNoRub = Math.max(preNoRub, preRub)
preRub = tempPreNoRub + nums[i]
}

return Math.max(preNoRub, preRub)
};
function rob(nums: number[]): number {
let before = 0, doubleBefore = 0
for (let i = 0; i < nums.length; i++) {
const temp = Math.max(before, doubleBefore + nums[i])
doubleBefore = before
before = temp
}
return before
};