动态规划是一种表格处理方法，它将原问题分解为若干子问题，自底向上先求解最小的子问题，并把结果存储在表格中，在求解大的子问题时直接从表格中查询小的子问题的解，以避免重复计算，从而提高效率。

动态规划算法常用来求解最优化问题，尤其是带有多步决策的最优化问题。此类最优化问题应具备以下3个要素。
（1）最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。也就是说一个问题的最优解只取决于其子问题的最优解。
（2）无后效性：将原问题分解为若干子问题，每个子问题的求解过程作为一个阶段，当前阶段的求解只与之前阶段有关，与之后阶段无关，即某阶段的状态一旦确定，就不受这个状态后续决策的影响。
（3）重叠子问题：求解过程中每次产生的子问题并不总是新问题，会有大量子问题重复。在遇到重复子问题时，只需在表格中查询，无须再次求解。该性质不是使用动态规划解决问题的必要条件，但是凸显了动态规划的优势。

动态规划解题的一般设计模式如下：
（1）划分阶段：按照问题的时间或空间特征，将问题分为若干个阶段。这也是动态规划状态转移的顺序，所以在划分阶段时，要注意划分后的阶段一定要有序或者是可排序的，以保证各状态的无后效性。
（2）定义状态：将问题发展到各个阶段时所处于的各种情况用不同的状态表示出来，通常状态的表示可以设为问题最终结果的一般化表示，并将最优解进行递归定义。
（3）决策与状态转移方程：在对问题的处理中做出的每种选择性的行动称为决策，即从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态。根据上一阶段的状态和决策来导出本阶段的状态就是状态转移。通常做法时根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
（4）边界条件：给出的状态转移方程时一个递推式，需要一个递推的终止条件或边界条件。

以斐波那契数列为例

要求第n项的值，首先要求第n-1,n-2项的值。