dp 就是动态规划的英文缩写，是一种解决复杂问题的算法思想，核心思路是把原本规模很大的原始问题，拆成一批互相关联的小规模子问题，先算出所有子问题的最优解并且保存下来，后续计算更大问题的时候直接复用已经算好的子问题结果，避免重复计算，以此大幅降低时间复杂度。很多初学者容易把 dp 和递归混淆，递归一般是从上往下拆解问题，会反复计算同一个子问题，存在大量冗余运算，动态规划大多是从最小子问题开始，自底向上逐步递推，把每一步的结果存入数组或者表格当中，适合求最优解计数方案数可行性判断这类问题，比如最短路径最大价值区间求和爬楼梯零钱兑换背包问题都是经典 dp 题型。

核心原理

动态规划能够成立有两个必备前提，第一个是最优子结构，意思是大问题的最优解，可以由它拆分出来的子问题的最优解组合得到，如果大问题最优解不能依靠子问题最优解推导，就不能使用 dp。第二个是重叠子问题，也就是拆分之后的子问题会被多次重复访问，这也是 dp 相比普通递归最大的优势，如果子问题全部独立没有重复，动态规划就没有提速意义。

在实际设计 dp 的时候，第一步要确定状态，状态一般用 dp 数组表示，dp 里面每一项代表对应规模或者对应条件下的答案，第二步写状态转移方程，也就是当前状态和前面若干个状态之间的数学关系，第三步确定初始边界条件，也就是最小子问题的已知答案，第四步确定遍历顺序，保证计算当前状态的时候，它依赖的前置状态已经提前计算完成，最后输出目标位置的 dp 值。

两种实现方式

设计 dp 的完整流程

第一步读懂题目，判断题型，确认题目是否满足最优子结构和重叠子问题，排除不能使用 dp 的题目。

第二步定义 dp 数组含义，这个是最关键的一步，定义错误后面转移方程全部会出错，要明确 dp [i] 或者 dp [i][j] 代表什么场景下的结果。

第三步推导状态转移方程，结合题目约束，思考当前状态可以从前面哪些状态转移而来，把选择取舍的逻辑写成等式。

第四步设置初始化，把最小下标或者边界位置的 dp 值提前赋值，这些是递推的起点。

第五步确定循环遍历顺序，一维 dp 一般从左往右，二维 dp 根据依赖关系选择从上到下从左到右，或者逆序遍历，逆序经常用在背包类 dp，防止重复使用同一个物品。

第六步校验，拿小规模样例手动模拟 dp 数组每一项的数值，确认转移逻辑没有错误，最后取出题目要求的最终答案。

dp 常见误区

很多人初学 dp 只会背模板，没有理解状态定义，遇到变形题目就无法写出转移方程。还有人忽略遍历顺序，二维 dp 或者背包 dp 顺序写反，得到错误结果。另外部分题目虽然看起来可以拆分，但是不满足最优子结构，强行套用 dp 会得到错误答案。dp 也不是万能算法，它一般会占用额外空间存储状态表，空间复杂度会高于暴力解法，部分题目还可以做空间优化，把二维 dp 压缩成一维 dp，减少内存占用。

【常见问题】

问题 1 dp 和普通递归最大区别是什么

回答 1 dp 也就是动态规划，和普通递归最大区别是 dp 会保存重叠子问题的计算结果，消除重复运算，普通递归每次遇到同一个子问题都会重新计算，时间效率更低。

问题 2 dp 一定需要二维数组吗

回答 2 dp 不一定需要二维数组，很多一维 dp 就可以解决爬楼梯这类问题，部分二维 dp 还可以通过滚动数组做空间优化压缩成一维 dp。

问题 3 什么样的题目不能使用 dp

回答 3 如果题目不存在重叠子问题，或者大问题最优解不能由子问题最优解组成，也就是不满足最优子结构，这类题目就不能使用 dp 求解。

问题 4 dp 的状态转移方程是什么

回答 4 dp 的状态转移方程就是描述 dp 数组当前项，依靠前面哪些子问题状态计算得到的数学关系式，是整个 dp 算法的核心。

【免责申明】

本文内容仅作为算法学习参考，不同编程场景题目存在特殊限制，实际编码请结合题目要求自行验证，不保证适配全部业务场景。