【内部资料】动态规划

动态规划法

动态规划法(Dynamic Programming Algorihm，DPA)类似于分治法，在 20 世纪 50 年代初由美国数学家 R.E.Bellman 发明，用于研究多阶段决策过程的优化过程与求得一个问题的最佳解动态规划法主要的做法是: 如果一个问题答案与子问题相关，就能将大问题拆解成各个小问题，其中与分治法最大不同的地方是可以让每一个子题的答案被存储起来，以供下次求解时直接取用。这样的做法不但能减少再次计算的时间，并可将这些解组合成大问题的解答，故而使用动态规划可以解决重复计算的问题

例如，前面斐波拉契数列采用的是类似分台法的递归法，如果改用动态规划法，那么已计算过的数据就不必重复计算了，也不会再往下递!-因而实现了提高性能的目的。如果我们想求斐波拉契数列的第 4 项数 Fib(4)，那么它的递归过可以用图 1-13 表示出来

从上面的执行路径图中我们可以得知递归调用了 9 次，而执行加法运算 4 次，Fib(1)与 Fib(0)共执行了3 次，重复计算影响了执行性能。我们根据动态规划法的思想，可以将算法修改如下(以C 语言为例)