动态规划（DP）是一种算法范式，通过子问题分解来求解原问题，并存储子问题的解，避免重复计算，提高效率。
子问题分解是一种通用的算法思路，在分治、动态规划、回溯中的侧重点不同。
- 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
- 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
- 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。
例题：爬楼梯
-
楼梯 阶，每次可上 或 阶，问有多少种爬法。
-
例如 时，共 种方案。
方法一：暴力搜索
-
思路：递归枚举所有可能路径。
-
缺点：存在大量 重叠子问题，复杂度 。
子问题的解法之和等于母问题（互相独立的组合数相加）：
方法二：记忆化搜索
-
“自顶向下” → 记忆化搜索：我们从原问题（根节点）开始，递归地将较大子问题分解为较小子问题，直至解已知的最小子问题（叶节点）。之后，通过回溯逐层收集子问题的解，构建出原问题的解。
-
思路：在递归基础上，使用
mem数组记录已算出的子问题。
-
优点：避免重复计算，复杂度优化到 。
方法三：动态规划, DP
-
“自底向上” → 动态规划：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。
-
由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。在以下代码中，我们初始化一个数组
dp来存储子问题的解，它起到了与记忆化搜索中数组mem相同的记录作用 -
将数组
dp称为 dp 表， 表示状态 对应子问题的最优解。 -
将最小子问题对应的状态（第 阶和第 阶楼梯）称为初始状态。
-
将递推公式 称为状态转移方程。
在动态规划问题中，当前状态往往仅与前面有限个状态有关，这时我们可以只保留必要的状态，通过“降维”来节省内存空间。这种空间优化技巧被称为“滚动变量”或“滚动数组”。
DP 要能用，核心是三个关键词：
-
重叠子问题：避免重复算。
-
最优子结构：大问题的最优解由小问题的最优解构成。
-
无后效性：未来状态只依赖现在，不依赖过去路径。
实用判断法：
-
先看能不能用回溯（穷举） 解决：符合“决策树模型”（一系列决策构成解）。
-
如果还带有“最大/最小/最优”的目标 → 更可能是 DP。
-
如果问题状态能抽象成数组/矩阵/树，并且相邻状态有递推关系 → DP 适合。