线性 DP：从爬楼梯到打家劫舍

一、面试常考点

1. 线性 DP 识别信号

答案和“前几个位置”的最优解相关。

2. 关键能力

能快速写出一维转移并做空间优化。

二、细节介绍

1. 爬楼梯

dp[i] = dp[i-1] + dp[i-2]。

2. 打家劫舍

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

3. 空间优化

只保留前两项，用两个变量滚动更新。

三、示例代码

function rob(nums) {
  if (nums.length === 0) return 0
  if (nums.length === 1) return nums[0]

  let prev2 = nums[0]
  let prev1 = Math.max(nums[0], nums[1])

  for (let i = 2; i < nums.length; i++) {
    const cur = Math.max(prev1, prev2 + nums[i])
    prev2 = prev1
    prev1 = cur
  }

  return prev1
}

四、常用应用场景

1. 一维最优决策

如每天做/不做某事的收益最大化。

2. 连续位置约束问题

如不能选相邻元素、隔天冷却等。