动态规划

动态规划（Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

同时动态规划也是运筹学的一个分支，是求解决策过程最优化的过程。

动态规划常常用于有重叠子问题和最优子结构性质的问题。

动态规划在求出子问题的解时，会将其存储起来，在下次遇到相同或相似的子问题时，能够直接查表得出其解，避免了重复多次求解这些子问题，从而减少计算量。

最优子结构

最优子结构是指子问题与原问题的关系。

当我们在求一个问题最优解的时候，可以把这个问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出原问题的最优解。

原问题的最优解由它的各个子问题的最优解所决定，这就是最优子结构。

在解题中一般用状态转移方程描述子问题的组合关系。例如：

$$f(n)=\{\begin{array}{ll}f(n-1)+f(n-2),& n=2k\\ f(n-1),& n=2k+1\end{array}$$

其中，$f(n)$ 为原问题的解（也叫状态），$f(n-1)+f(n-2)$ 描述了一种子问题组合关系。$n=2k$ 和 $n=2k+1$ 表示原问题上的不同选择，不同的选择可能对应不同的子问题组合关系。

通过这个状态转移方程，我们能够很快写出问题求解的递归实现。

重叠子问题

重叠子问题是指子问题之间的关系。

当我们在递归地求解每个子问题的最优解时，可能会遇到相同或类似的子问题，如果我们不做处理，则会出现许多重复的计算，动态规划会把求出的子问题的解存储起来，在下次遇到相同或相似的子问题时，能够直接查表得出其解，避免了重复多次求解这些子问题，减少重复计算。

例如，斐波那契数列的状态转移方程 $f(n)=f(n-1)+f(n-2)$。在求 $f(5)$ 时，需要先求子问题 $f(4)$ 和 $f(3)$，得到结果后再组合成原问题 $f(5)$ 的解。递归地求 $f(4)$ 时，又要先求子问题 $f(3)$ 和 $f(2)$ ，这里的 $f(3)$ 与求 $f(5)$ 时的子问题重复了。

总结

解决动态规划问题的核心：找出子问题之间以及子问题与原问题的关系。

实际就是以下两个要点：

• 找出状态转移方程；
• 避免状态重复计算。

动态规划步骤：

1. 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题；
2. 设计子问题的递归描述方式；
3. 证明对原问题的最优解包括了对所有子问题的最优解；
4. 证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）。

References

• 动态规划