动态规划是一种解决优化问题的算法思想，其要领是将问题分解为子问题，并通过保存子问题的解来避免重复计算。运用条件包括：
1.问题具有最优子结构性质，即问题的最优解可以由子问题的最优解推导得到；
2.子问题之间存在重叠，即子问题之间的求解存在重复计算；
3.问题满足无后效性，即某个阶段的状态一旦确定，就不受后续决策的影响。动态规划广泛应用于求解最短路径、背包问题、序列比对等各种优化问题。
最优子结构性质和子问题重叠性质是该问题可用动态规划算法求解的基本要素：
1.最优子结构
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。
在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
2.重叠子问题
可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要此子问题时，只要简单地用常数时间查看一下结果。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。
