基本概念

动态规划（dynamic programming），可称为动态表格法。和分治一样，通过组合子问题的解来求解原问题，但是分治求解的是互不相交的子问题，动态规划求解的是相互重叠的子问题。不过分治算法会做出许多重复的不必要的计算，而动态规划会将每次求解的子问题动态保存在表格内，避免不必要的工作。

算法步骤

  • 刻画一个最优解的结构特征。（定义状态方程）
  • 递归地定义最优值的解。（对状态初始化，并编写状态转移式子）
  • 计算最优解的值，通常采用自底向上的方法。（从表格初始化点开始进行状态转移，动态填写表格）
  • 利用计算出的信息构造一个最优解。（取出表格中最终得出的最优解结果）

两种实现方法

自顶向下法

自顶向下法又可称为记忆化搜索。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解，当每次要使用到子问题的解时，会搜索每个子问题的解，减少重复的运算。由于递归会先递归到最深处，所以称为自顶向下法。

# 代码实现 (以斐波那契数列为例)
def MEMOIZED_CUT_ROD_AUX(n, r):
    if r[n-1] >= 0:
..........0000000000000000000000000000000    r[n-1] = MEMOIZED_CUT_ROD_AUX(n - 1, r) + MEMOIZED_CUT_ROD_AUX(n - 2, r)
    return r[n-1]

if __name__ == '__main__':
    r = [-1] * 14
    r[0] = 0
    r[1] = 1
    print(MEMOIZED_CUT_ROD_AUX(14, r))  # 233

自底向上法

这种方法一般需要恰当定义子问题，使得任何子问题的求解都只依赖于“更小的子问题”。因此在求解最优解时，会依次求解规模从小到大的子问题，每个子问题的最优解都依赖于子子问题的最优解，最终得出整个问题的最优解，也由此被称为自底向上法。

# 代码实现 (以斐波那契数列为例)
def BOTTOM_UP_CUT_ROD(n, r):
    for i in range(2, n):
        r[i] = r[i - 1] + r[i - 2]
    return r[n - 1]

if __name__ == '__main__':
    r = [-1] * 14
    r[0] = 0
    r[1] = 1
    print(BOTTOM_UP_CUT_ROD(14, r))  # 233

两种方法对比

  • 通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快（时间复杂度相同，相差一个常数系数），因为自底向上的算法没有递归调用的开销，表的维护开销也更小(指对表的访问次数少 这里可以想想斐波那契数列两种方法的访问次数)。
  • 但是如果子问题空间中某些子问题不需要完全求解，备忘方法就会体现出优势了，因为它只会求解那些绝对必要的子问题。

两个经典例子分析

链条分解问题

矩阵连乘问题

动态规划原理

本质

动态规划的本质为利用求解问题的最优子结构和子问题重叠性质。

最优子结构

何为最优子结构？

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。在使用动态规划时，我们用子问题的最优解来构造原问题的最优解。

但是最优子结构是怎么发掘的？

  1. 对给定的问题，做出的一个选择能够产生一个或多个待解的子问题，同时子问题又能做出选择继续产生子问题，最终分解为最小子问题。（比如链条切割问题，选定链条划分位置，而被划分的链条能继续划分）
  2. 在第一步选择中，通常我们已经知道了哪种选择是最优解了。（初始化最小子问题）
  3. 我们知道如何从所有子问题得到这些子问题的原问题的最优解。
  4. 子问题的刻画应尽可能简单，在必要的时候拓展。因为一个问题的子问题规模会决定时间复杂度。（如链条分解问题子问题数目为n，矩阵连乘问题子问题为n^2）
  5. 子问题之间应该是无关的 即同一个原问题的一个子问题的解不影响另一个子问题的解。 思考无权最短路和无权最长路问题的区别。（求解一个子问题用到一些资源，导致这些资源在求解其他子问题时不可用 求最长路径时子问题可能包含另一个子问题的顶点）

重叠子问题

如果在算法中求解问题时，存在子问题被反复求解，则称该问题具有重叠子问题性质。动态规划利用这一性质，当第一次求解一个子问题时，便动态地将解存储在一个表格中，在下次需要该子问题时，直接从表格中查找。

重构最优解

在解决问题时，通过动态规划，我们可以很好的找出这个问题的答案。但是如果我们想要知道答案的选择过程时，便需要去检查所有的可能，造成大量的查找时间。这种情况下，根据典型的时空权衡原则，我们可以再使用一个表格，在每次对子问题做出选择时，便记录下我们的选择。通过记录下的选择，我们可以很好的重构出最优解，并只需要O（1）的时间。

动态规划与贪心

两者相似的地方在于技巧性地设计子问题，都需要具有最优子结构的性质。

动态规划复用子问题的解，每次都将子 问题的解保存下来，方便下次复用，而每个子问题也依赖于它的子问题，最终堆叠出问题的最优解，本质还是穷举，复杂度高。

而贪心每次都能排除一堆子问题。它不需要复用子问题的解，当前最优解从子问题最优解即可得出。整个过程是线性的推导过程，复杂度低，但得出的不一定是最优解。