线性 DP：爬楼梯、最小花费与打家劫舍

线性 DP：爬楼梯、最小花费与打家劫舍

前端高频算法原题解析.pdf 的动态规划部分包含爬楼梯、最小花费爬楼梯和最大子数组和；这些题与打家劫舍共享“只依赖有限前缀”的线性 DP 模型。面试时先写一句状态定义，再推导最后一步，最后判断能否滚动压缩。

一、识别信号与统一步骤

看到“走到第 i 位的方案数/最小代价/最大收益”“连续子数组最优值”时，可按以下顺序建模：

1. 定义状态：dp[i] 必须是一句完整、无歧义的话；
2. 按最后一步分类：列出进入 i 的所有合法来源，得到转移；
3. 初始化边界：尤其确认 n = 0、第一步是否收费、全负数是否允许；
4. 确定答案位置：答案可能在 dp[n]、dp[n - 1] 或所有状态的最大值；
5. 检查依赖宽度：只依赖前两项时可压到 O(1)，否则保留完整表。

二、爬楼梯：计数型线性 DP

1. 题面与状态

每次走 1 或 2 阶，求到达第 n 阶的方案数。定义 dp[i] 为走到第 i 阶的方案数，则最后一步来自 i - 1 或 i - 2：

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

本实现约定“走到 0 阶有 1 种空方案”，因此 n = 0 返回 1；若题面明确 n 为正整数，这个分支不会影响正常输入。

function climbStairs(n) {
  if (!Number.isInteger(n) || n < 0) {
    throw new RangeError('n must be a non-negative integer')
  }
  if (n === 0) return 1
  if (n === 1) return 1

  let twoBack = 1 // dp[0]
  let oneBack = 1 // dp[1]
  for (let step = 2; step <= n; step += 1) {
    const current = oneBack + twoBack
    twoBack = oneBack
    oneBack = current
  }
  return oneBack
}

时间复杂度 O(n)，额外空间 O(1)。如果 n 很大，方案数会超过安全整数，应改用 BigInt 或模运算，并在接口中明确返回类型：

function climbStairsMod(n, mod) {
  if (!Number.isInteger(n) || n < 0) {
    throw new RangeError('n must be a non-negative integer')
  }
  if (!Number.isInteger(mod) || mod <= 0) throw new RangeError('invalid mod')
  let twoBack = 1 % mod
  let oneBack = 1 % mod
  for (let step = 2; step <= n; step += 1) {
    const current = (oneBack + twoBack) % mod
    twoBack = oneBack
    oneBack = current
  }
  return n === 0 ? twoBack : oneBack
}

三、最小花费爬楼梯：顶点状态与“楼顶”边界

1. 题面与状态

cost[i] 是踩上第 i 阶的花费，可以从第 0 或第 1 阶开始，最后要到数组之外的楼顶。定义 dp[i] 为到达位置 i（位置 n 表示楼顶）的最小花费。到达 i 的最后一步可能从 i - 1 或 i - 2 来：

dp[i] = min(dp[i - 1] + cost[i - 1],
           dp[i - 2] + cost[i - 2])

这种定义避免对输入执行 cost.push(0)，也不会把楼顶误当成需要收费的台阶。

function minCostClimbingStairs(cost) {
  if (!Array.isArray(cost) || cost.length < 2) {
    throw new RangeError('cost must contain at least two steps')
  }
  if (cost.some((value) => !Number.isFinite(value) || value < 0)) {
    throw new RangeError('cost values must be non-negative numbers')
  }

  let twoBack = 0 // 到达位置 0，不需先踩任何台阶
  let oneBack = 0 // 到达位置 1，也可从地面直接开始

  for (let position = 2; position <= cost.length; position += 1) {
    const current = Math.min(
      oneBack + cost[position - 1],
      twoBack + cost[position - 2]
    )
    twoBack = oneBack
    oneBack = current
  }
  return oneBack
}

minCostClimbingStairs([10, 15, 20]) // 15
minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) // 6

每个位置只计算一次，时间 O(n)、额外空间 O(1)。常见错误是把 cost[i] 加在“离开”而不是“踩上”台阶的时机，或直接修改输入数组；回答时要说明楼顶下标是 cost.length，该位置没有 cost。

四、最大子数组和：Kadane 的状态不变量

1. 题面与推导

给定至少一个整数，求连续子数组的最大和。定义 endingHere 为必须以当前位置结尾的最大和，则当前位置只有两种选择：

• 把当前值接到前一个最优后面：endingHere + value；
• 放弃前缀，从当前值重新开始：value。

因此 endingHere = max(value, endingHere + value)，并用 best 保存所有结尾状态的最大值。这里不能把初值设为 0，否则全负数组会错误返回 0。

function maxSubArray(nums) {
  if (!Array.isArray(nums) || nums.length === 0) {
    throw new RangeError('nums must contain at least one number')
  }

  let endingHere = nums[0]
  let best = nums[0]
  for (let index = 1; index < nums.length; index += 1) {
    const value = nums[index]
    endingHere = Math.max(value, endingHere + value)
    best = Math.max(best, endingHere)
  }
  return best
}

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) // 6
maxSubArray([-5, -2, -8]) // -2

时间 O(n)，额外空间 O(1)。不变量是：处理完下标 i 后，endingHere 恰为所有以 i 结尾的连续子数组中的最大和，best 恰为下标 0..i 范围内的全局最大和。若需要返回区间，额外记录 candidateStart、bestStart、bestEnd，在“重新开始”时更新起点。

function maxSubArrayRange(nums) {
  if (!nums.length) return null
  let sum = nums[0]
  let best = nums[0]
  let candidateStart = 0
  let bestStart = 0
  let bestEnd = 0

  for (let index = 1; index < nums.length; index += 1) {
    if (nums[index] > sum + nums[index]) {
      sum = nums[index]
      candidateStart = index
    } else {
      sum += nums[index]
    }
    if (sum > best) {
      best = sum
      bestStart = candidateStart
      bestEnd = index
    }
  }
  return { sum: best, start: bestStart, end: bestEnd }
}

五、打家劫舍：不相邻选择

定义 dp[i] 为前 i 间房屋可获得的最大金额。第 i 间要么不偷（dp[i - 1]），要么偷并跳过相邻房（dp[i - 2] + nums[i]）：

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

function rob(nums) {
  if (!Array.isArray(nums)) throw new TypeError('nums must be an array')
  let twoBack = 0
  let oneBack = 0

  for (const amount of nums) {
    const current = Math.max(oneBack, twoBack + amount)
    twoBack = oneBack
    oneBack = current
  }
  return oneBack
}

若金额允许负数，通常仍可选择不偷，初值 0 表示空集合；若题目要求至少选择一间，需要改变边界定义，不能直接复用此代码。

六、常见追问与边界

Q: 为什么爬楼梯可以压成两个变量？

A: 当前状态只依赖 i - 1 和 i - 2，更早状态不会再被读取；滚动变量保存这两个依赖即可。若需要恢复具体路径，则必须保留前驱或完整表。

Q: 最小花费题为什么不能简单返回 dp[n - 1]？

A: dp[n - 1] 表示踩到最后一个台阶的代价，目标是走到数组之外的楼顶；最后一步可以从 n - 1 或 n - 2 跨出，因此答案是 dp[n]。

Q: Kadane 为什么不是遇到负数就清零？

A: 清零的写法只有在允许空子数组且答案下限为 0 时才成立。题面通常要求至少一个元素，全负数组必须返回最大的负数，所以状态应从 nums[0] 初始化。

Q: DP 和贪心如何区分？

A: DP 会保留多个可能前缀的最优状态并按转移合并；贪心只保留一个局部选择，必须额外证明该选择不会损失全局最优。打家劫舍若只“看到偶数位就偷”并不成立，状态转移才覆盖所有合法选择。

七、练习检查清单

• n = 0/1/2、费用为零、第一步和第二步都可开始。
• 最大子数组含单元素、全负数、全正数、最优区间在首尾。
• 打家劫舍空数组、单间、金额为零或负数时契约是否明确。
• 不修改输入数组，不把超出安全整数的方案数悄悄当成精确 Number。
• 先说状态语义和不变量，再说 O(n) 时间、O(1) 额外空间及路径恢复代价。

来源：前端高频算法原题解析.pdf 的“爬楼梯”“最小花费爬楼梯”“最大子序和”；与项目原有动态规划方法论融合整理。

相关专题：动态规划方法论、动态规划基础速览、状态机 DP。