钉子的生活日记
文章目录

动态规划学习与实践笔记

适合目标：系统掌握动态规划的核心思维、状态设计方法、经典题型套路与面试表达。
学习定位：这一份偏“从入门到会做题，再到能总结套路”。
学习原则：先理解为什么能用动态规划，再学状态定义和转移方程，最后通过经典题把套路练熟。

目录

  1. 学习总览
  2. 动态规划到底是什么
  3. 动态规划适用条件
  4. 动态规划的解题五步法
  5. 线性 DP
  6. 背包 DP
  7. 子序列 DP
  8. 区间 DP
  9. 股票 DP
  10. 树形 DP 与状态压缩 DP 入门
  11. 经典题实战
  12. 高频面试题
  13. 学习路线建议
  14. 一页速记总结
  15. 背诵口诀

1. 学习总览

1.1 动态规划到底在学什么

很多人一开始学动态规划会有几个明显感受：

  1. 题目看懂了，但不知道状态怎么定义
  2. 能看懂答案，但自己推不出转移方程
  3. 同样是 DP，换个题型就不会了

本质上，动态规划学的不是“题海”，而是下面这套思维：

把一个大问题拆成若干个有重叠的子问题，并且把子问题答案存下来，避免重复计算。

你要逐渐形成一个意识：

  1. 暴力递归是在“重复求解子问题”
  2. 动态规划是在“记住已经求过的结果”
  3. 真正的难点不是写代码，而是“状态设计”

1.2 动态规划的核心主线

主线 1：状态

当前问题处于什么阶段。

主线 2：选择

当前这一步可以做哪些决策。

主线 3：转移

当前状态怎么从之前的状态推出来。

主线 4：边界

最小子问题怎么初始化。

主线 5：答案

最终结果从哪个状态取。

1.3 学习顺序建议

建议按这个顺序学：

  1. 爬楼梯、斐波那契
  2. 打家劫舍
  3. 最大子数组和
  4. 不同路径
  5. 0-1 背包
  6. 最长递增子序列
  7. 最长公共子序列
  8. 编辑距离
  9. 区间 DP
  10. 股票 DP

2. 动态规划到底是什么

2.1 一句话定义

动态规划可以理解成：

把原问题拆成一系列有重叠子问题，利用状态转移逐步求解最优值、方案数或可行性。

2.2 为什么叫“动态规划”

这里的“动态”不是动来动去，而是：

  1. 问题会随着阶段推进不断变化
  2. 我们是按阶段逐步推出答案

“规划”可以理解为：

  1. 先定义状态
  2. 再设计转移
  3. 最后有计划地填表

2.3 动态规划和递归的关系

动态规划经常来自递归。

很多题的思考顺序是：

  1. 先写暴力递归
  2. 发现重复子问题
  3. 用记忆化搜索优化
  4. 再改成 DP 表

所以可以记住一句话：

动态规划通常是对暴力递归的优化。

2.4 和贪心的区别

  1. 贪心是每一步都选当前最优
  2. 动态规划是综合历史状态后得出全局最优

并不是所有最优问题都能贪心，很多只能 DP。

3. 动态规划适用条件

动态规划通常适用于下面两个条件：

3.1 最优子结构

大问题的最优解，可以由子问题的最优解推出。

例如：

  1. 走到第 i 阶的最少花费
  2. 长度为 i 的最优值

3.2 重叠子问题

递归过程中会反复计算同样的子问题。

例如：

  1. f(5) 会算 f(4) 和 f(3)
  2. f(4) 又会继续算 f(3) 和 f(2)

3.3 不满足这两个条件会怎样

  1. 没有重叠子问题，可能分治更合适
  2. 没有最优子结构，DP 可能推不出来

4. 动态规划的解题五步法

这是最重要的一节。

4.1 第一步：定义 dp

先回答：

dp[i] 或 dp[i][j] 到底表示什么。`

这一步最关键。
如果状态定义错了，后面全错。

常见定义方式：

  1. dp[i] 表示到第 i 个位置的最优值
  2. dp[i][j] 表示考虑前 i 个物品、容量为 j 时的最优值
  3. dp[i][j] 表示字符串前 i 个字符和前 j 个字符的答案

4.2 第二步：写状态转移方程

也就是：

当前状态如何由之前状态推出来

例如：

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

或者：

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

4.3 第三步：初始化

初始化决定最小子问题的答案。

常见边界：

  1. dp[0] = 0
  2. dp[1] = 1
  3. 第一行第一列特殊处理

4.4 第四步：确定遍历顺序

核心原则：

在计算当前状态前，它依赖的状态必须已经算出来。

例如：

  1. 从左到右
  2. 从上到下
  3. 倒序遍历

4.5 第五步：返回答案

答案不一定总是 dp[n]。

可能是：

  1. dp[n]
  2. dp[m][n]
  3. max(dp[i])

5. 线性 DP

线性 DP 是最基础的一类，状态通常沿着数组或序列线性推进。

5.1 斐波那契数列

定义：

dp[i] 表示第 i 个斐波那契数。

转移：

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

代码：

function fib(n) {
  if (n < 2) return n

  const dp = new Array(n + 1).fill(0)
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  return dp[n]
}

5.2 爬楼梯

定义：

dp[i] 表示爬到第 i 阶的方法数。

转移：

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

5.3 打家劫舍

定义：

dp[i] 表示偷到下标 i 位置时，前 i 个房子能获得的最大金额。

转移：

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

代码：

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

  const dp = new Array(n).fill(0)
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])

  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
  }

  return dp[n - 1]
}

5.4 最大子数组和

定义：

dp[i] 表示以 nums[i] 结尾的最大子数组和。

转移：

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

这个题很适合理解：

状态不一定表示前 i 个元素的答案，也可以表示“必须以 i 结尾”的答案。

6. 背包 DP

背包是动态规划里的大头。

6.1 0-1 背包问题

问题：

给定若干物品，每个物品只能选一次，背包容量有限，求最大价值。

状态定义：

dp[i][j] 表示前 i 个物品中，容量为 j 时的最大价值。

转移：

  1. 不选第 i 个物品
  2. 选第 i 个物品
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

6.2 一维优化

因为 dp[i][j] 只依赖上一层，所以可以压缩成一维：

function knapsack(weights, values, bagSize) {
  const dp = new Array(bagSize + 1).fill(0)

  for (let i = 0; i < weights.length; i++) {
    for (let j = bagSize; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i])
    }
  }

  return dp[bagSize]
}

要点：

0-1 背包一维优化时，容量必须倒序遍历。

6.3 完全背包

区别：

每个物品可以使用无限次。

遍历方式：

容量正序遍历。

6.4 组合与排列

这是背包里最爱考的变形。

如果问：

  1. 有多少种组合
  2. 有多少种排列

就要注意：

  1. 先物品后背包，通常算组合
  2. 先背包后物品，通常算排列

7. 子序列 DP

7.1 最长递增子序列

定义：

dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。

转移：

if nums[i] > nums[j]
dp[i] = max(dp[i], dp[j] + 1)

代码：

function lengthOfLIS(nums) {
  const n = nums.length
  const dp = new Array(n).fill(1)
  let ans = 1

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
    ans = Math.max(ans, dp[i])
  }

  return ans
}

7.2 最长公共子序列

定义：

dp[i][j] 表示字符串 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。

转移：

  1. 如果当前字符相等，来自左上角
  2. 否则来自上方或左方最大值
if text1[i - 1] === text2[j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

7.3 编辑距离

定义：

dp[i][j] 表示把 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。

核心操作：

  1. 插入
  2. 删除
  3. 替换

这是经典二维 DP。

8. 区间 DP

区间 DP 常见于：

  1. 回文串
  2. 合并石子
  3. 戳气球

8.1 最长回文子串思路

定义：

dp[i][j] 表示区间 [i, j] 是否是回文串。

转移：

  1. s[i] === s[j]
  2. 且内部区间也是回文

8.2 区间 DP 的关键

遍历顺序通常不是普通从前往后，而是：

  1. 先枚举区间长度
  2. 再枚举区间起点

因为大区间依赖小区间。

9. 股票 DP

股票题是面试高频大类。

9.1 只允许买卖一次

状态可以定义为：

  1. 持有股票时的最大收益
  2. 不持有股票时的最大收益

9.2 多次买卖

继续维护这两个状态，但每天都更新。

9.3 含冷冻期、手续费

就是在原有状态基础上继续加限制条件。

股票 DP 的核心不是死记题，而是掌握：

把“持股 / 不持股 / 冷冻期”等抽象成状态。

10. 树形 DP 与状态压缩 DP 入门

10.1 树形 DP

树形 DP 就是在树结构上做动态规划。

常见特点：

  1. 每个节点的状态依赖子节点
  2. 常用后序遍历

典型题：

  1. 二叉树打家劫舍
  2. 树上最大独立集

10.2 状态压缩 DP

适合：

  1. 数据范围不大
  2. 状态可以用二进制表示

常见于：

  1. 集合选取
  2. 旅行商问题
  3. 小规模排列组合问题

这类题属于进阶方向，先会基础 DP 再碰。

11. 经典题实战

11.1 不同路径

问题：

从左上角走到右下角，每次只能向右或向下，有多少种走法。

定义：

dp[i][j] 表示走到格子 (i, j) 的路径数。

转移：

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

代码：

function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1))

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }

  return dp[m - 1][n - 1]
}

11.2 最小路径和

定义：

dp[i][j] 表示从起点走到 (i, j) 的最小路径和。

转移：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

11.3 零钱兑换

问题：

给定面额数组和目标金额，求最少硬币数。

定义：

dp[i] 表示凑成金额 i 所需的最少硬币数。

转移：

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

代码：

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount]
}

11.4 编辑距离

这个题的重点是理解：

  1. 删除
  2. 插入
  3. 替换

都如何对应到 dp[i - 1][j]、dp[i][j - 1]、dp[i - 1][j - 1]。

12. 高频面试题

12.1 什么是动态规划

答题模板：

动态规划是一种把原问题拆分成重叠子问题，并通过保存子问题结果来避免重复计算的算法思想。它通常适用于具有最优子结构和重叠子问题的问题。

12.2 动态规划和递归、贪心有什么区别

  1. 递归可能会重复计算子问题
  2. 动态规划会记住已经求过的结果
  3. 贪心是局部最优策略，动态规划是综合历史状态求全局最优

12.3 动态规划最难的地方是什么

最难的是：

  1. 状态定义
  2. 转移方程
  3. 遍历顺序

代码本身通常不难。

12.4 怎么判断题目能不能用动态规划

看两个条件：

  1. 是否有最优子结构
  2. 是否有重叠子问题

12.5 0-1 背包为什么要倒序遍历

因为一维优化时，倒序才能保证每个物品只被使用一次。
如果正序，会导致同一轮里重复使用当前物品。

12.6 二维 DP 的常见套路是什么

  1. 字符串匹配
  2. 网格路径
  3. 区间问题
  4. 两个序列之间的关系

12.7 如何从暴力递归推到动态规划

推荐答法：

先写递归，找出参数和重复子问题，再把递归参数转成状态数组，最后按照依赖关系确定初始化和遍历顺序。

13. 学习路线建议

13.1 入门阶段

先做这些题：

  1. 斐波那契
  2. 爬楼梯
  3. 打家劫舍
  4. 最大子数组和
  5. 不同路径

13.2 提升阶段

再做这些：

  1. 0-1 背包
  2. 完全背包
  3. 最长递增子序列
  4. 最长公共子序列
  5. 编辑距离

13.3 进阶阶段

最后补：

  1. 区间 DP
  2. 股票 DP
  3. 树形 DP
  4. 状态压缩 DP

13.4 刷题原则

  1. 一类题先学模板
  2. 再做变形题
  3. 每做完一题都写清楚状态和转移
  4. 不要只记答案代码

14. 一页速记总结

14.1 动态规划五问

每做一道题，先问自己 5 个问题：

  1. dp 定义是什么
  2. 状态怎么转移
  3. 初始化是什么
  4. 遍历顺序是什么
  5. 最终答案从哪取

14.2 常见状态定义

  1. dp[i]：到位置 i 的答案
  2. dp[i][j]：两个维度共同决定的答案
  3. dp[i][0/1]：是否持有、是否选取等二元状态

14.3 常见题型

  1. 线性 DP
  2. 背包 DP
  3. 子序列 DP
  4. 区间 DP
  5. 股票 DP
  6. 树形 DP

15. 背诵口诀

先定状态，再写转移；先想边界，再定顺序；大题拆小题，重复就记忆。