动态规划可视化
动态规划先定义较小的子问题，按依赖顺序求解，再复用答案，避免重复计算。本组从最小的重叠子问题开始，逐步学习优化问题中的填表方式。
不要只记递推公式。先说明一个格子代表什么、可以读取哪些旧状态，以及填表顺序为什么保证它们已经可用。
如何阅读动态规划课程
观察三个问题：
- 状态的含义：斐波那契的
dp[i]是fib(i)；LCS 的dp[i][j]是两个前缀的最长公共子序列长度；编辑距离的同类格子是两个前缀间最少编辑次数；0/1 背包的dp[i][w]是前i件物品在容量w下的最大价值。 - 读取哪些旧状态：斐波那契读左边两格；LCS 读上、左或左上；编辑距离读取三者并加上对应操作成本；背包读上一行，以及上一行较小容量处。读错位置会改变算法。
- 答案还要恢复什么：有时只需最终数值，LCS 和背包等还要回溯，恢复具体序列或选择。
复杂度比较
| 课程 | 状态形状 | 核心概念 | 时间 | 演示空间 |
|---|---|---|---|---|
| 斐波那契与记忆化 | 递归树／一维表 | 重叠子问题 | 记忆化后 O(n) | O(n) |
| 零钱兑换 | 一维表 | 多种硬币中的最小值，对比贪心 | O(amount * coins) | O(amount) |
| 最长公共子序列 | 二维前缀表 | 对齐字符串并回溯 | O(m * n) | O(m * n) |
| 编辑距离 | 二维前缀表 | 最少插入、删除或替换脚本 | O(m * n) | O(m * n) |
| 0/1 背包 | 二维表 | 容量限制下取或不取 | O(n * capacity) | O(n * capacity) |
斐波那契说明缓存为何有用，零钱兑换让每格在多个候选中选择，LCS 加入第二个输入维度，编辑距离为相邻状态赋予操作含义，背包则用二维状态约束物品选择。
建议学习顺序
先学斐波那契与记忆化。朴素递归树会重复相同调用，缓存消除重复，再切到自底向上填表，看调用树如何变成一行格子。
再学零钱兑换。每格从多个硬币选择中取最小值。演示先运行贪心，让“先拿最大面额”的失败可见；回溯具体硬币也为后面的背包做准备。
最长公共子序列的两条轴都是字符串前缀。字符匹配时扩展左上角答案，不匹配时保留上方或左方较长的结果。回溯把右下角的长度还原成字符，也展示不同最优路径可以产生不同有效子序列。
编辑距离保留前缀网格，但上、左、左上分别对应删除、插入、替换。除了右下角的数，还要回溯最短脚本，最后重放脚本，检查是否真的生成目标字符串。
最后学 0/1 背包。右下角给出价值，回溯给出物品。严格读取上一行，保证同一物品不会重复使用；状态定义因此也承担约束作用。
全部动态规划可视化课程
逐步执行递推，在复杂画面暂停，说明当前格子的含义，以及它使用了哪些已完成的答案。