Dynamic Programming，动态编程。
找最优解的系统方法，利用递归，自顶向下拆分，将问题拆解成子问题，并放入二维空间，子问题的最优解放入线性空间中。求得子问题的最优解之后，逐步向上，找到原始问题的最优解。
适用于动态规划问题，有以下特征：
- 优化问题，要找一个最优解。
- 重叠子问题，一个大问题，可以被逐步拆分成子结构
- 最优子结构，每个子问题都有最优解，所有的最优解组合在一起就找到了整体问题的最优解
- 无后效性，处理一个子步骤，无须了解之前和之后的步骤，只需要关注问题的转化结构即可。
步骤
第一步：明确问题的状态，并处理好状态。可以用函数一个函数表示，例如 f(X)
第二步：设计状态转移方程。表示状态间的转移关系。一般的状态转移方程包含了当前步骤对之前步骤的递归，因为是优化问题，所以方程一般包含一个 max() 或者 min() 函数用以取最优方案。
第三步：编程，并明确问题中的重复部分，用缓存来处理。
自顶向下的递归方法
由于使用了状态转移方程，方程中表示的最优子结构展开后是一个树形的递归结构。而因为使用了缓存，树形结构中叶子结点无须重复计算。
自顶向下的方法和我们日常生活里使用的思维方式不同。日常一般利用自底向上方法，从0-1的过程处理问题。而递归则先定义结果，然后从结果拆分到最初始的状态。递归的拆分方式更适合计算机处理，而自底向上更适合人类的“从初始条件到结果”的逻辑推理。
可解决的问题
按照动态规划问题的特征，01背包问题，最短路径问题和找钱问题，以及这些问题的等价问题，都可以用动态规划来解决。
很多问题都可以等效为最短路径问题。这里有一个直觉，例如 0-1背包问题和最大子序和问题。最短路径是一个由图组成的路径搜索，而动态规划则是一个制表的过程，直观体现为在表中找一个最短路径。
计算复杂度理论
动态规划可以极大的减少计算复杂度，以上问题如果使用暴力搜索解决，一般会有O(n^3)以上的复杂度，然而，若使用动态规划，根据状态转移方程的不同，可以有：
- 线性复杂度：O(n) ，如果状态转移方程只包含一个变量。
- 平方复杂度：O(n^2)，如果状态转移方程包含两个变量。
总体来说，复杂度应为 O(m*n) ，m 为状态数量，n 为问题的输入规模大小。
这里计算复杂度的直觉，可以认为比起暴力搜索，动态规划保存了所有最优子结构的中间过程，而免去了部分中间计算。