动态规划（Dynamic Programming，简称 DP）是一种把大问题拆成若干互相重叠的小问题、把每个小问题的答案记下来反复使用，从而避免重复计算的解题方法。它的名字里有“规划”，实际做的却是“记账”。
两个前提，缺一不可
DP 能不能用，只看两件事：
最优子结构（optimal substructure）：大问题的最优解，可以由小问题的最优解拼出来。求 A 到 C 的最短路径，如果经过 B，那么 A 到 B、B 到 C 这两段也必须各自最短。
重叠子问题（overlapping subproblems）：不同的分支会反复遇到同一个小问题。
以斐波那契数列为例：算 fib(5) 要 fib(4) 和 fib(3)，算 fib(4) 又要 fib(3) 和 fib(2)——同一个 fib(3) 被算了两遍，往下每一层都在重复。朴素递归的调用次数随 n 指数增长，而把算过的结果存进一张表，每个值只算一次，就降成线性。
打个生活化的比方：做一桌菜，聪明的做法是先切好一盘葱、炖好一锅高汤，贴上标签放那儿，谁要用直接取；笨做法是每道菜都从剥葱开始。DP 就是那张“半成品清单”。
实现上有两种写法，本质相同：自顶向下的记忆化搜索（memoization，递归 + 缓存），和自底向上的填表（tabulation，按依赖顺序递推）。前者写起来贴近思路，后者省去递归开销。
和相邻概念的区别
关键点：不是所有递归都能 DP。递归只是一种写法，DP 描述的是问题的性质。
| 方法 | 子问题是否重叠 | 是否缓存 | 典型场景 |
|---|---|---|---|
| 朴素递归 | 常常重叠但不缓存 | 否 | 斐波那契直接递归 |
| 分治（divide and conquer） | 不重叠，各管各的 | 不需要 | 归并排序、二分查找 |
| 动态规划 | 重叠 | 是 | 编辑距离、背包问题 |
| 贪心（greedy） | 不回头重算 | 否 | 每一步取局部最优 |
分治和 DP 最容易混：归并排序把数组劈成两半，左右两半互不相干，缓存没有意义；而 DP 的子问题是同一批被反复问到的，缓存才有价值。贪心则要求更强的条件，每步只留一个选择、不做回溯；DP 保留所有候选状态，能解贪心搞不定的题，代价是状态空间可能很大。
对从业者的意义
DP 在工程里出现得比想象中多：文本编辑器的 diff、拼写纠错、DNA 序列比对、语音识别里的维特比解码（Viterbi）、强化学习里的值迭代，背后都是同一套“定义状态 + 写状态转移方程”的思路。
真正难的是第一步——想清楚“状态”是什么，也就是“要做出下一步决策，我此刻最少需要记住哪些信息”。这一步定了，转移方程和填表顺序往往水到渠成。
对不写代码的人也一样：做预算、排项目，先问一句“哪些中间结果值得记下来复用”，通常比每次从零重算省事得多。
至于各类框架与库的具体实现细节，以官方文档为准。