动态规划：C++算法界的“记忆超人”，让你的代码从“递归到死”到“秒出答案”！

动态规划：C++算法界的“记忆超人”，让你的代码从“递归到死”到“秒出答案”！

友情提示：本文阅读时长约30分钟，建议搭配咖啡或肥宅快乐水。读完后若电脑没冒烟，恭喜你——DP已初步入门！若电脑冒烟了……咳，建议先重启，再重读本文第5遍。

---

开篇：我与DP的“相爱相杀”史（别笑，你肯定也这样！）

还记得我第一次接触动态规划（Dynamic Programming，简称DP）的场景吗？那是一个阳光明媚的下午，我对着屏幕上的斐波那契数列问题，自信满满地写下了递归代码：

int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); // 看我多优雅！}

结果呢？当n=40时，我的MacBook Pro发出了“核爆级”风扇声，屏幕温度计都快冒烟了。我急得直薅头发：“这破电脑是不是该换硅胶套了？”
直到隔壁工位的老王（一个头发稀疏但眼神犀利的算法老炮）探头一笑：“小伙子，你这是在用‘递归’自杀啊！试试DP吧，它能让你的代码从‘龟速’变‘光速’！”

这就是DP的魔力——它像一个记性超群的老奶奶，把所有算过的答案都记在小本本上，下次再遇到同样的问题，直接翻本本就行，绝不重复劳动！
而C++？它就是那个能帮你把“小本本”写得又快又省的硬核工具。今天，咱就用接地气的语言、真实的C++代码，把DP这头“纸老虎”扒得底裤都不剩！保证让你读完后拍大腿：“原来DP这么简单？！”

---

一、DP是什么？别被名字吓到，它就是个“聪明懒人”！

1.1 名字的真相：冷战时期的“营销鬼才”

“动态规划”这名字一听就高大上，仿佛能操控宇宙能量。但真相是——它根本和“动态”没啥关系！
1950年代，数学家Richard Bellman研究这类问题时，国防部拨款紧张，一听“研究”就头大。Bellman灵机一动：“不如叫‘规划’？听起来像搞经济建设！” 为了显得更“动态”，他硬塞了个Dynamic（动态）。
翻译成人话：这名字就是个“标题党”，本质就是记住答案，避免重复计算。就像你妈让你收拾房间：

• 递归：你先收拾书桌（花10分钟），再收拾书桌（又花10分钟）…因为记性差，反复收拾同一张桌子。
• DP：你把书桌、床、地板都标好号，收拾完书桌就记下来“书桌已干净”，下次直接跳过。省时省力，还能偷懒刷抖音！

1.2 为什么DP这么牛？两个核心“超能力”

DP能成为算法界扛把子，全靠两大绝技：

1. 重叠子问题（Overlapping Subproblems）
   问题能拆成小问题，但这些小问题会反复出现。
   举个栗子：斐波那契数列f(n) = f(n-1) + f(n-2)。

   • 计算f(5)时：
     f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
   • 看到没？f(3)算了两次，f(2)算了三次！递归就像个健忘症患者，算一遍忘一遍。
   • DP的解法：把f(0)到f(5)的结果存在数组里，算过就存，下次直接取。
     

2. 最优子结构（Optimal Substructure）
   大问题的最优解，必须由小问题的最优解拼出来。
   举个接地气的例子：从家到公司，最短路径一定经过某个地铁站。如果到地铁站的路不是最短，那到公司的路肯定也不是最短！

   • DP的思路：先算到每个地铁站的最短路，再拼出全程最短路。
   • 反例：贪心算法就像“只看眼前”——每次选最近的地铁站，结果可能绕远路（比如贪心选了“五道口”，结果堵成狗）。

✨ 关键总结：

• 有重叠子问题 → DP能省时间（避免重复计算）
• 有最优子结构 → DP能得正确解（小最优拼大最优）
  一句话：DP就是“拆问题 + 记答案 + 拼最优”的三板斧！

1.3 DP vs 递归 vs 分治：别再傻傻分不清！

• 递归：
  • 优点：代码短，像讲故事一样自然。
  • 缺点：重复计算多，fib(40)能算到你怀疑人生。
  • 适用：子问题不重叠时（比如归并排序）。
• 分治：
  • 优点：大问题拆独立小问题，各算各的。
  • 缺点：小问题不重叠，没法共享结果（比如快速排序）。
• DP：
  • 优点：小问题重叠时，速度吊打递归。
  • 缺点：得手动设计“记答案”的方式（有点烧脑）。
  • 灵魂比喻：
    

    递归是“单机游戏”，每次重开存档；
    分治是“多人副本”，队友各打各的；
    DP是“云存档”，全服共享进度！

---

二、DP三板斧：从“懵圈”到“秒懂”的实战指南

2.1 第一板斧：定义状态——给问题贴“标签”

状态（State）就是描述问题当前情况的变量。设计状态时，记住：

“状态越少越好，能少写一个变量就少写一个！”

案例：爬楼梯问题（经典入门题）

题目：每次能爬1阶或2阶，爬n阶楼梯有几种方法？

• 错误状态：dp[i][j]表示爬到第i阶、上一步走了j阶的方法数 → 变量太多，自己都绕晕！
• 正确状态：dp[i]表示爬到第i阶的方法数 → 简单粗暴！
• 为什么？ 因为到第i阶只取决于前两阶（i-1和i-2），和之前怎么爬无关（马尔可夫性）。

2.2 第二板斧：状态转移方程——DP的“灵魂公式”

转移方程就是如何从旧状态推出新状态。推导秘诀：

“假设你已经知道所有小问题的答案，怎么用它们拼出大问题的答案？”

继续爬楼梯：

• 到第i阶，最后一步要么是1阶（从i-1来），要么是2阶（从i-2来）。
• 所以：dp[i] = dp[i-1] + dp[i-2]
• 边界条件：dp[0]=1（0阶只有1种方法：不动），dp[1]=1（1阶只有1种）。

再看背包问题（DP扛把子）：

题目：n个物品，重量w[]，价值v[]，背包容量W，求最大价值。

• 状态：dp[i][j]表示前i个物品、容量j时的最大价值。
• 转移方程：
  • 不选第i个：dp[i][j] = dp[i-1][j]
  • 选第i个：dp[i][j] = dp[i-1][j - w[i]] + v[i]（需j >= w[i]）
• 最终：dp[i][j] = max(不选, 选)
• 边界：dp[0][j]=0（没物品时价值为0）

2.3 第三板斧：计算顺序——别让电脑“等答案”

DP有两种实现方式，核心区别是计算顺序：

方法 Top-Down（记忆化搜索） Bottom-Up（递推） 思路 递归 + 缓存结果 从小到大迭代计算 代码风格 像递归，但加了缓存 纯循环，填表格 优点 逻辑清晰，只算需要的状态 无递归开销，空间可控 缺点 递归栈可能溢出 需手动设计顺序 适用场景 状态稀疏（如某些树形DP） 状态密集（如背包）

用斐波那契演示两种写法：

Top-Down（记忆化搜索）：

#include using namespace std;int fib_topdown(int n, vector<int>& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; // 如果算过，直接返回 memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo); // 否则计算并存 return memo[n];}int fib(int n) { vector<int> memo(n+1, -1); // 初始化记忆数组，-1表示未计算 return fib_topdown(n, memo);}

幽默解读：这就像你问老奶奶“f(5)是多少？”，老奶奶翻本本：“f(4)和f(3)还没算呢！” 然后她先算f(4)…算完记下来，下次直接说“f(5)=5”。

Bottom-Up（递推）：

int fib_bottomup(int n) { if (n <= 1) return n; vector<int> dp(n+1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; // 从小到大填表 } return dp[n];}

幽默解读：这像老奶奶的“填表格日常”：周一算f(0)，周二算f(1)，周三算f(2)…到周五直接报f(5)=5。优点：不用来回翻本本，一气呵成！

✨ 新手必看：

• 初学者优先用Bottom-Up！递归容易栈溢出，填表逻辑更直观。
• 记住：“状态定义决定成败，转移方程是命门，计算顺序定生死！”

---

三、C++实现DP：用好STL，让代码又快又省

3.1 数组 vs Vector：别在内存上栽跟头！

C++的优势就是精细控制内存，DP中常用：

容器 适用场景 代码示例 注意事项 数组 状态维度固定、大小已知 int dp[1000][1000]; 避免越界！全局数组自动初始化0 Vector 大小动态变化（如n不确定） vector<vector> dp(n+1, vector(W+1, 0)); 初始化方便，但可能慢一点

背包问题C++实现（Bottom-Up）：

#include #include using namespace std;int knapsack(int n, int W, vector<int>& w, vector<int>& v) { // dp[i][j]：前i个物品，容量j时的最大价值 vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); for (int i = 1; i <= n; i++) { // 遍历每个物品 for (int j = 0; j <= W; j++) { // 遍历每个容量 dp[i][j] = dp[i-1][j]; // 不选当前物品 if (j >= w[i-1]) { // 注意：w,v下标从0开始 dp[i][j] = max(dp[i][j], dp[i-1][j - w[i-1]] + v[i-1]); } } } return dp[n][W];}

关键注释：

• w[i-1]：因为vector下标从0，但dp中i表示“前i个物品”
• j >= w[i-1]：容量够才能选
• 时间复杂度：O(nW)，空间复杂度：O(nW)

3.2 空间优化：从O(n²)到O(n)甚至O(1)！

大问题时，O(n²)空间可能爆内存。优化思路：

“只存必要的状态，旧的赶紧扔！”

斐波那契空间优化：
原Bottom-Up需要O(n)数组，但其实只用存前两个数：

int fib_optimized(int n) { if (n <= 1) return n; int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; // 当前值 a = b; // 更新前两个值 b = c; } return b;}

空间复杂度：O(1)！就像老奶奶只带一个小便签，算完就撕旧纸。

背包问题空间优化（滚动数组）：
观察转移方程：dp[i][j]只依赖dp[i-1][*]。所以只用两行数组：

int knapsack_optimized(int n, int W, vector<int>& w, vector<int>& v) { vector<int> dp(W+1, 0); // 只用一维数组！ for (int i = 0; i < n; i++) { // 遍历每个物品 for (int j = W; j >= w[i]; j--) { // 重点：倒序遍历！ dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } return dp[W];}

为什么倒序？
正序会覆盖后续需要的数据（比如j=3时更新了dp[3]，但算j=5时需要旧的dp[3]）。
空间复杂度：O(W)，从O(n*W)降到O(W)！
[图片：滚动数组示意图。显示一维dp数组在迭代中的变化：初始全0 → 物品1后[0,6,6,6,6,6] → 物品2后[0,6,10,10,16,16]…]

3.3 避坑指南：C++ DP的“死亡陷阱”

1. 数组越界：

   • 错误：dp[i][j]中i从1开始，但w[i]越界（因为w下标0开始）。
   • 解法：统一用w[i-1]，或定义dp时dp[n+1][W+1]。

2. 初始化错误：

   • 背包问题中，dp[0][j]=0必须初始化，否则结果乱码。
   • 解法：用vector(size, 0)初始化。

3. 顺序搞反：

   • 背包优化时正序遍历 → 结果错误（因为覆盖了旧值）。
   • 解法：牢记“一维优化必倒序”。

4. 递归爆栈：

   • Top-Down时n太大（如n=10000），递归深度超限。
   • 解法：改用Bottom-Up，或增大栈空间（不推荐）。

血泪教训：上次我写LCS（最长公共子序列）时，把dp[i][j] = dp[i-1][j-1] + 1写成dp[i][j] = dp[i][j] + 1，结果程序算出个“外星人序列”！面试官问我：“这串火星文是啥？” 我：……（默默重启IDE）

---

四、经典DP问题实战：从入门到“装X”

4.1 斐波那契数列：DP的“Hello World”

• 问题：求f(n)，f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)
• DP解法：Bottom-Up填表，O(n)时间，O(1)空间（优化后）
• 为什么重要：理解重叠子问题的绝佳案例。

// 终极优化版（O(1)空间）int fib(int n) { if (n < 2) return n; int a = 0, b = 1; for (int i = 2; i <= n; i++) { tie(a, b) = make_pair(b, a + b); // C++17结构化绑定，超帅！ } return b;}

幽默测试：

• n=0 → 0（正确）
• n=1 → 1（正确）
• n=40 → 102334155（0.001秒出结果，电脑风扇：？？？）
  对比递归版：n=40时，你的电脑可能已经去见爱因斯坦了。

4.2 0-1背包问题：DP的“扛把子”

• 问题：n个物品，重量w[]，价值v[]，背包容量W，求最大价值（每个物品选或不选）。
• 状态：dp[i][j] = 前i个物品、容量j时的最大价值
• 转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
• 优化：滚动数组 → O(W)空间

实战案例：

• 物品：w = {2, 3, 4, 5}, v = {3, 4, 5, 6}, W=8
• 手动填表（关键步骤）： i\\j 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 1 0 0 3 3 3 3 3 3 3 2 0 0 3 4 4 7 7 7 7 3 0 0 3 4 5 7 8 9 9 4 0 0 3 4 5 7 8 9 10
• 结果：dp[4][8]=10（选物品1和4：w=2+5=7, v=3+6=9？不对！再看表：实际选物品2和3：w=3+4=7, v=4+5=9？等等…）
  纠错：表中i=4,j=8时，dp[4][8]=max(dp[3][8]=9, dp[3][3]+6=4+6=10) → 选物品4和物品2（w=5+3=8, v=6+4=10）！
  

  [图片：背包问题DP表格填色图。用绿色标出最优路径：从(4,8)→(3,3)→(2,3)→(1,0)，对应选物品4和2。]

完整C++代码（带详细注释）：

#include #include #include using namespace std;int main() { int n = 4, W = 8; vector<int> w = {2, 3, 4, 5}; // 物品重量 vector<int> v = {3, 4, 5, 6}; // 物品价值 // 滚动数组：dp[j]表示容量j时的最大价值 vector<int> dp(W + 1, 0); for (int i = 0; i < n; i++) { // 倒序遍历容量（关键！） for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } // 打印当前dp数组（调试用） cout << \"After item \" << i+1 << \": \"; for (int j = 0; j <= W; j++) cout << dp[j] << \" \"; cout << endl; } cout << \"Max value: \" << dp[W] << endl; // 输出10 return 0;}

运行输出：
After item 1: 0 0 3 3 3 3 3 3 3
After item 2: 0 0 3 4 4 7 7 7 7
After item 3: 0 0 3 4 5 7 8 9 9
After item 4: 0 0 3 4 5 7 8 9 10
Max value: 10
看！每一步都清晰可见，再也不用“盲调”了！

4.3 最长公共子序列（LCS）：字符串DP的“试金石”

• 问题：给两个字符串s1, s2，求最长公共子序列（如\"ABCBDAB\"和\"BDCABA\"的LCS是\"BCBA\"）。
• 状态：dp[i][j] = s1前i字符和s2前j字符的LCS长度
• 转移方程：
  • 如果s1[i-1]==s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
  • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 边界：dp[0][j]=0, dp[i][0]=0

手动填表演示：
s1=“ABC”, s2=“AC”

i\\j 0 A C 0 0 0 0 A 0 1 1 B 0 1 1 C 0 1 2

• 结果：LCS长度=2（“AC”）

C++实现（带路径回溯）：

#include #include #include using namespace std;string lcs(string s1, string s2) { int m = s1.size(), n = s2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 填DP表 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } // 回溯找LCS string res = \"\"; int i = m, j = n; while (i > 0 && j > 0) { if (s1[i-1] == s2[j-1]) { res = s1[i-1] + res; i--; j--; } else if (dp[i-1][j] > dp[i][j-1]) { i--; } else { j--; } } return res;}int main() { string s1 = \"ABCBDAB\", s2 = \"BDCABA\"; cout << \"LCS: \" << lcs(s1, s2) << endl; // 输出 BCBA return 0;}

幽默调试：

• 如果输出\"BCAB\"？检查回溯时是否优先走了dp[i-1][j]（应优先相等字符）。
• 如果输出空？检查字符串下标（C++从0开始，dp表从1开始）。

4.4 编辑距离（Levenshtein Distance）：DP的“高阶实战”

• 问题：将字符串A转成B，最少操作数（插入、删除、替换）。
• 状态：dp[i][j] = A前i字符转B前j字符的最小操作数
• 转移方程：
  • 删除A[i]：dp[i][j] = dp[i-1][j] + 1
  • 插入B[j]：dp[i][j] = dp[i][j-1] + 1
  • 替换/相等：dp[i][j] = dp[i-1][j-1] + (A[i]!=B[j] ? 1 : 0)
• 边界：dp[i][0]=i, dp[0][j]=j

案例：A=“kitten”, B=“sitting” → 编辑距离=3（k→s, e→i, 插入g）
DP表关键部分：

“” s i t t i n g “” 0 1 2 3 4 5 6 7 k 1 1 2 3 4 5 6 7 i 2 2 1 2 3 4 5 6 t 3 3 2 1 2 3 4 5 t 4 4 3 2 1 2 3 4 e 5 5 4 3 2 2 3 4 n 6 6 5 4 3 3 2 3

C++代码（含空间优化）：

int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<int> dp(n+1); // 初始化第一行 for (int j = 0; j <= n; j++) dp[j] = j; for (int i = 1; i <= m; i++) { int prev = dp[0]; // 保存dp[i-1][j-1] dp[0] = i; // 更新dp[i][0] for (int j = 1; j <= n; j++) { int temp = dp[j]; // 保存旧的dp[i-1][j] if (word1[i-1] == word2[j-1]) { dp[j] = prev; // 相等时，操作数不变 } else { dp[j] = min({dp[j] + 1, // 删除 dp[j-1] + 1, // 插入 prev + 1}); // 替换 } prev = temp; // 更新prev为dp[i-1][j] } } return dp[n];}

空间优化精髓：

• 用prev变量记住dp[i-1][j-1]，避免二维数组。
• 复杂度：O(m*n)时间，O(n)空间。
  测试：minDistance(\"kitten\", \"sitting\") → 返回3，正确！

---

五、DP优化大招：从“能跑”到“飞起”

5.1 空间优化：内存省出一个G

• 滚动数组：适用于状态只依赖前几行（如背包、LCS）。
  技巧：
  • 二维变一维：dp[j]覆盖dp[i-1][j]
  • 倒序遍历：防止覆盖（背包问题核心！）
• 状态压缩：用位运算存状态（如状态机DP）。
  案例：n皇后问题，用int mask表示列占用，空间从O(n²)降到O(1)。

5.2 时间优化：剪枝与提前终止

• 可行性剪枝：如果当前状态已不可能优于最优解，直接跳过。
  背包例子：在循环中加if (dp[j] + max_possible_value < current_best) continue。
• 单调队列优化：用于多重背包（O(nW) → O(nlogW)）。
  核心思想：用双端队列维护滑动窗口最大值。

多重背包C++片段（单调队列优化）：

// 伪代码：对每个物品，按模w[i]分组for (int r = 0; r < w[i]; r++) { // r是余数 deque<int> dq; // 双端队列存索引 for (int j = r; j <= W; j += w[i]) { // 维护队列：移除过期元素（超出数量限制） while (!dq.empty() && j - dq.front() > k[i] * w[i]) dq.pop_front(); // 移除队尾更差的元素 while (!dq.empty() && dp_old[dq.back()] + (j - dq.back())/w[i]*v[i] <= dp_old[j]) dq.pop_back(); dq.push_back(j); dp_new[j] = dp_old[dq.front()] + (j - dq.front())/w[i]*v[i]; }}

看不懂？没关系！ 记住：“当数量k大时，用单调队列；k小时，直接拆成0-1背包”。

5.3 特殊技巧：四边形不等式优化

• 适用问题：区间DP（如石子合并、最优二叉搜索树）。
• 核心：若满足w[i][j] + w[i+1][j+1] <= w[i][j+1] + w[i+1][j]，则转移点单调。
• 效果：O(n³) → O(n²)
• C++实现：维护K[i][j]表示最优分割点，K[i][j-1] <= K[i][j] <= K[i+1][j]。

石子合并代码片段：

for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; dp[i][j] = INT_MAX; // 优化：k从K[i][j-1]到K[i+1][j] for (int k = K[i][j-1]; k <= K[i+1][j]; k++) { int cost = dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1]; if (cost < dp[i][j]) { dp[i][j] = cost; K[i][j] = k; // 记录最优分割点 } } }}

5.4 实战：如何选择优化策略？

问题类型 推荐优化 效果 斐波那契类 滚动变量（O(1)空间） 从O(n)到O(1) 0-1背包 滚动数组（一维+倒序） 从O(nW)到O(W) 多重背包（k大） 单调队列 从O(nkW)到O(nW) 区间DP 四边形不等式 从O(n³)到O(n²) 状态稀疏问题 记忆化搜索+哈希表 只算需要的状态

血泪经验：

• 面试时先写朴素DP，再提优化（展示思路清晰）。
• 比赛时直接上优化（省时间就是省生命）。

---

六、DP常见陷阱：别掉进这些“坑”里！

6.1 状态定义错误：方向错了，再努力也白搭

• 案例：最长递增子序列（LIS）
  • 错误状态：dp[i] = 以i结尾的LIS长度 → 正确
  • 更错状态：dp[i] = 前i个元素的LIS长度 → 错误！因为LIS不一定以i结尾。
• 解法：

  int lengthOfLIS(vector<int>& nums) { int n = nums.size(), res = 0; vector<int> dp(n, 1); // dp[i]: 以nums[i]结尾的LIS长度 for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i])  dp[i] = max(dp[i], dp[j] + 1); } res = max(res, dp[i]); } return res;}

6.2 边界条件遗漏：程序崩溃的“隐形杀手”

• 案例：爬楼梯问题
  • 忘记dp[0]=1 → n=0时结果错。
  • 解法：写代码前先列边界：
    

    n=0 → 1种（不动）
    n=1 → 1种（爬1阶）
    n=2 → 2种（1+1或2）

6.3 复杂度误判：以为O(n)其实是O(n²)

• 案例：用map代替vector存状态
  • 以为map查询O(1)，实际O(log n) → 整体O(n log n)而非O(n)。
• 解法：
  • 优先用数组/vector（连续内存，缓存友好）。
  • 用unordered_map时注意哈希冲突。

6.4 调试技巧：打印DP表，让错误无处遁形

• 黄金法则：

  // 调试背包问题for (int i = 0; i <= n; i++) { for (int j = 0; j <= W; j++) { cout << dp[i][j] << \" \"; } cout << endl;}

• 进阶：用Python生成热力图（面试时别真用，但自己debug超好用）。

真实故事：上次我写股票买卖问题，结果输出负数。打印DP表后发现：
dp[0][1] = -prices[0]写成了dp[0][1] = prices[0]。
从此我牢记：“DP表打印三行，Bug退散！”

---

七、DP学习路线图：从新手到“面试收割机”

7.1 新手村（1周）：打牢基础

1. 必刷题：
   • 斐波那契数列（理解重叠子问题）
   • 爬楼梯（状态定义）
   • 0-1背包（二维DP入门）
2. 目标：能手写背包代码，解释转移方程。

7.2 冒险平原（2周）：经典问题

1. 必刷题：
   • 最长公共子序列（LCS）
   • 最长递增子序列（LIS）
   • 编辑距离
2. 目标：掌握一维优化，能画DP表。

7.3 高级副本（3周）：优化与实战

1. 必刷题：
   • 多重背包（单调队列）
   • 石子合并（四边形不等式）
   • 股票买卖系列（状态机DP）
2. 目标：能口述优化思路，解决LeetCode Hard题。

7.4 面试技巧：如何优雅地装X

• 话术模板：
  

  “这个问题有重叠子问题和最优子结构，适合用DP。我定义状态dp[i]表示…，转移方程是…。空间上可以用滚动数组优化到O(1)。”

• 避坑：
  • 别一上来就说“用DP”，先分析是否满足条件。
  • 说不清时，先写递归+记忆化（Top-Down），再提Bottom-Up优化。

真实案例：
面试官：“如何求最小路径和？”
我：“先定义dp[i][j]为到(i,j)的最小和，转移dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。空间优化可以用一维数组，倒序更新…”
面试官：“…你被录用了。”

---

八、总结：DP不是魔法，是“懒人”的智慧

动态规划，说白了就是用空间换时间的“聪明懒人哲学”：

• 递归：像拼命三郎，重复劳动到吐血。
• DP：像精明老奶奶，记小本本+高效复用，省时省力。

在C++中实现DP，关键就三点：

1. 状态定义要精简（变量越少越好）
2. 转移方程要写对（假设小问题已解决）
3. 计算顺序要合理（Bottom-Up优先，一维优化必倒序）

最后送你一句话：

“DP学得好，面试没烦恼；DP学得精，offer拿到手软；DP学不会……电脑风扇先冒烟！”

别怕DP烧脑，多画表格、多写代码，它就是纸老虎。现在，关掉这篇文章，打开IDE，写个斐波那契DP——让电脑风扇安静地跑出f(10000)。等你成功了，回来评论区喊一句：“DP，不过如此！”

---

附录：DP学习资源推荐

• 书籍：《算法导论》第15章（硬核但全面）
• 网站：LeetCode DP Tag（300+题，按难度刷）
• 视频：MIT 6.006 Dynamic Programming（B站有中字）
• 工具：VisuAlgo DP可视化（画表格神器）

字数统计：本文约9850字（含代码、图片描述），保证让你读得爽、学得会！
版权声明：本文原创，转载需授权。但允许你打印出来贴在工位上，每天默念三遍：“DP，你只是个纸老虎！”

彩蛋：
为什么DP程序员最怕过年？
因为亲戚问：“工资多少？”
他答：“我用DP算过，最优解是…保密！”
亲戚：“？？？”
他：“咳，就是…比你儿子多一点。” 😎