对于第[i] 个房子,我们抢还是不抢。
的问题。就是当前的房子可以抢的价值 + dp[i - 2]
i - 1 不能抢,否则会触发警铃
dp[i - 1]
.这里的 dp 其实就是子问题
.
dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
(注:这里为了方便计算,令 dp[0]
和 dp[1]
都等于 0,所以 dp[i]
对应的是 nums[i - 2]
)动态规划问题是递归问题查表,避免重复计算,从而节省时间。 如果我们对问题加以分析和抽象,有可能对空间上进一步优化
与 JavaScript 代码略有差异,但状态迁移方程是一样的。