手帐 Blog

主题

21 · DP 入门 · 一维 ​

目标：会定义一维状态与转移方程；独立写出爬楼梯、打家劫舍。

为什么面试会考 ​

动态规划（DP）听起来吓人，面试前端常考入门一维：

  • 爬楼梯、斐波那契同构
  • 打家劫舍：选或不选
  • 零钱兑换：完全背包味道

考的是：你会不会说「dp[i] 表示什么」，而不是背模板名词。

零基础概念 ​

三步：

  1. 状态：dp[i] 的含义（用一句话说清）
  2. 转移：dp[i] 怎么由更小的状态算出来
  3. 初始化 + 答案位置：dp[0]/dp[1]；答案是 dp[n] 还是 min(dp)？

重叠子问题用数组（或滚动变量）存起来，避免重复递归。

JS 模板：一维递推 ​

js
const dp = Array(n + 1).fill(0)
dp[0] = /* 初值 */
for (let i = 1; i <= n; i++) {
  dp[i] = /* 用 dp[i-1] ... */
}
return dp[n]

空间优化：若只依赖前两项，用两个变量滚动。

精讲题 ​

LeetCode 70. 爬楼梯 ​

到第 i 阶：从 i-1 走 1 步，或从 i-2 走 2 步。

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

js
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n <= 2) return n
  let a = 1
  let b = 2
  for (let i = 3; i <= n; i++) {
    const c = a + b
    a = b
    b = c
  }
  return b
}

LeetCode 198. 打家劫舍 ​

不能偷相邻。对第 i 家：

  • 偷：dp[i-2] + nums[i]
  • 不偷：dp[i-1]

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

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const n = nums.length
  if (n === 0) return 0
  if (n === 1) return nums[0]
  let prev2 = 0
  let prev1 = 0
  for (let i = 0; i < n; i++) {
    const cur = Math.max(prev1, prev2 + nums[i])
    prev2 = prev1
    prev1 = cur
  }
  return prev1
}

LeetCode 322. 零钱兑换 ​

dp[a] = 凑成金额 a 的最少硬币数；无法凑成记 Infinity。

js
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const dp = Array(amount + 1).fill(Infinity)
  dp[0] = 0
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a >= c) dp[a] = Math.min(dp[a], dp[a - c] + 1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}

练习清单 ​

题提示
LeetCode 509. 斐波那契数同爬楼梯
LeetCode 746. 使用最小花费爬楼梯从 0 或 1 起；取 min
LeetCode 213. 打家劫舍 II环：拆成「偷第一不偷最后」两段
LeetCode 139. 单词拆分dp[i] 前 i 能否拆

今日验收 ​

  • [ ] 70 / 198 能口述状态与转移
  • [ ] 322 能解释为何 dp[0]=0、其余初值 Infinity
  • [ ] 知道「先定义含义再写转移」

若你以前见过 ​

斐波那契递推就是最简单的 DP；面试别只说「斐波那契」，要说 dp[i] 含义。