算法导论—动态规划_最优子结构

华电北风吹
天津大学认知计算与应用重点实验室
日期：2015/8/27

首先区分动态规划和分治策略。
这两者有很相似的地方，都是通过组合子问题的解来求解原问题。不同的是，分治策略将原问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题(子问题的求解是递归进行的，将其划分为更小的子问题)。在这种情况下，分治法会做许多不必要的工作，他会反复求解那些公共的子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个字子问题时都需要重新计算，避免了这种不必要的计算工作。
——算法导论第15章

分治对应的常用方法：
快速排序、最大子数组问题、归并排序、矩阵乘法的Strassen算法
动态规划对应的常用方法：
钢条切割问题、矩阵链乘法、最长公共序列(LCS)、最优二叉搜索树

一、动态规划初探
通过计算斐波那契数列的第n项展示动态规划两种等价的实现方法(1&2)：
0、自顶向下递归实现

def Fibonacci(n):
    if n==0:
        return 0
    if n<3:
        return 1
    return Fibonacci(n-1)+Fibonacci(n-2)
1
2
3
4
5
6

1、带备忘的自顶向下法：

def Fibonacci(n):
    k=d.get(n)
    if k==None:
        result=Fibonacci(n-1)+Fibonacci(n-2)
        d[n]=result
        return result
    return k
d={0:0,1:1,2:1}
1
2
3
4
5
6
7
8

2、自底向上法：

def Fibonacci(n):
    if n==0:
        return 0
    if n<3:
        return 1
    a,b=1,1
    for i in range(2,n):
        c=a+b
        a,b=b,c
    return c
1
2
3
4
5
6
7
8
9
10

二、动态规划原理
动态规划要解决的问题：多阶段决策过程最优化问题
适合用动态规划求解的最优化问题应该具有的两个要素：最优子结构和子问题重叠
1、最优子结构
最优子结构：如果一个问题的最优解包含子问题的最优解，我们就称此问题具有最优子结构特征。
具有最优子结构的问题，我们求解子问题的最优解才有意义。(贪心算法也要求最优子结构)
2、子问题重叠
如果递归算法反复求解相同的子问题，我们就成最优化问题具有重叠子问题。与之相对的，适合分治方法求解的问题通常在每一步都会生成一个全新的子问题。(这里与分治法的子问题不相交不同)
具有子问题重叠的问题，我们采用自顶向上的动态规划才能够减少计算量。