动态规划是一个重要的算法范式，它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。
动态规划问题特性#
子问题分解是一种通用的算法思路，在分治，动态规划，回溯中的侧重点不同。
- 分治算法递归地将问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到元问题的解。
- 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
- 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分之。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。
动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构，无后效性 - 最优子结构的定义：原问题的最优解是从子问题的最优解构建得来。
- 无后效性：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。
动态规划解题思路#
考虑以下两个问题：
- 如何判断一个问题是不是动态规划问题？
- 求解动态规划问题该从何处入手，完整步骤是什么？
问题判断#
如果一个问题包含重叠子问题，最优子结构，并满足无后效性，那么它通常适合用动态规划求解。
通常我们会放宽条件，先观察问题是否适合用回溯解决。适合用回溯解决的问题通常满足 “决策树模型 “，这种问题可以使用树形结构来描述，其中每一个节点代表一个决策，每一条路径代表一个决策序列。
换句话说，如果问题包含明确的决策概念，并且解是通过一系列决策产生的，那么它就满足决策树模型，通常可以使用回溯来解决。
在此基础上，动态规划问题还有一些判断的 “加分项”：
- 问题包含最大（小）或最多（小）等最优化描述
- 问题的状态能使用一个列表，多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。
相应的也存在一些 “减分项 “： - 问题的目标是找出所有可能的解决方案，而不是找出最优解
- 问题描述中有明显的排列组合的特征，需要返回具体的多个方案。
问题求解步骤#
动态规划的解题流程会因问题的性质和难度而有所不同，但通常遵循以下步骤：描述决策，定义状态，建立 dp 表，推导状态转移方程，确定边界条件等。