#03动态规划

要点：

动态规划方法与贪心法、分治法的异同；

动态规划方法的基本要素与求解步骤；

动态规划方法的应用。

难点：

如何根据问题的最优子结构性质构造构造动态规划方法中的递归公式或动态规划方程。

动态规划的基本思想

动态规划的实质

1) 分治思想：将原问题分解为更小、更易求解的子问题，然后对子问题进行求解，并最终产生原问题的解。

2) 解决冗余：求解过程中，所有子问题只求解一次并以表的方式保存，对于相同子问题并不重复求解而通过查表的方式获得。

动态规划和分治法的异同

1) 相同：都基于分治思想；

2) 不同：分治法中各个子问题是独立的，而动态规划方法中允许子问题之间存在重叠。

动态规划的3个基本要素

1）最优子结构性质：（F(5)的最优解包括F(4)的最优解）

问题最优解包含其子问题的最优解。为动态规划的基础。基于最优子结构性质导出递归公式或动态规划基本方程是解决一切动态规划问题的基本方法。反证法证明。

2) 子问题重叠性质：（F(3)和F(2)被多次求解）

求解过程中有些子问题出现多次而存在重叠。第一次遇到就加以解决并保存，若再次遇到时无需重复计算而直接查表得到，从而提高求解效率。该性质不是必要条件，但无该性质该方法即没有优势。

3) 自底向上的求解方法：（Fibonacci数的第二种求解方法）

鉴于子问题重叠性质，采用自底向上的方法。先填停止条件，求解每一级子问题并保存，直至得到原问题的解

//斐波那契数列自顶向下递归求解: 
FIB1(n)  
IF n = 0     
   RETURN 0   
ELSE IF n = 1     
   RETURN 1   
ELSE 
   RETURN FIB1(n-1) + FIB1(n-2)
//时间复杂性为O(1.618n)，空间复杂性为O(n)。

//自底向上求解伪代码： 
FIB2(n)
  F[0] = 0 //F[0..n]
  F[1] = 1
  FOR i = 2 TO n
      F[i] = F[i-1] + F[i-2]
 RETURN F[n]
//其时间复杂性为O(n)，空间复杂性为O(n)。

动态规划求解的4个基本步骤

（1）分析最优解的性质，以刻画最优解的结构特征 ——— 考察是否适合采用动态规划方法，即是否具备最优子结构性质；

（2）递归定义最优值（即建立递归公式或动态规划方程），包括停止条件（递归出口）和递归体；

（3）以自底向上的方式计算出最优值，并记录相关信息。应充分利用子问题重叠性质；

（4）最终构造出最优解。

备忘录方法(动态规划方法的变形)

相同点：用表格保存已经解决的子问题的解，下次需要时直接查表而无需重新计算；

不同点：①备忘录方法采用自顶向下的递归方式，动态规划是采用自底向上的递归方式；

②备忘录的控制结构和直接递归的结构同，区别在于备忘录方法为已有解的子问题建立备忘录待需要时查看；

最长公共子序列LCS问题

设序列X={ $x_1$ , $x_2$ ,…, $x_m$ }和Y={ $y_1$ , $y_2$ ,…, $y_n$ }的最长公共子序列为Z={ $z_1$ , $z_2$ ,…, $z_k$ } ，则：

若 $x_m$ == $y_n$ ，则 $z_k$ == $x_m$ == $y_n$ ，而且 $z_{k-1}$ 是 $x_{m-1}$ 和 $y_{n-1}$ 的最长公共子序列；

若 $x_m$ ≠ $y_n$ 且 $z_k$ ≠ $x_m$ ，则 $Z$ 是 $X_{m-1}$ 和 $Y$ 的最长公共子序列；

若 $x_m$ ≠ $y_n$ 且 $z_k$ ≠ $y_n$ $y_n$ ，则 $Z$ 是 $X$ 和 $Y_{n-1}$ 的最长公共子序列。

以上，可以使用反证法进行证明。

LCS满足动态规划的条件：

LCS问题的子问题重叠性质：在计算X和Y的LCS时，可能需要计算 $X_{m-1}$ 和 $Y$ 或 $X$ 和 $Y_{n-1}$ 的LCS，很显然都包含了 $X_{m-1}$ 和 $Y_{n-1}$ 的LCS。

LCS问题的最优子结构性质建立子问题最优值的递归关系：

用c[i][j]记录序列Xi和Yj的LCS的长度。其中，Xi={x1,x2,…,xi}和Yj={y1,y2,…,yj}分别为序列X和Y的第i个前缀和第j个前缀。当i=0或j=0时，空序列是Xi和Yj的LCS。此时C[i][j]=0。其他情况下，由最优子结构性质可建立递归关系。

LCS问题的具体设计：

①确定合适的数据结构。采用二维数组c来存放各个子问题的最优解，二维数组b记录各子问题最优值的来源（之前的递归公式上所附注的以上3种情况）

②初始化。令c[i][0]=0,c[0][j]=0，其中，0≤i≤m，0≤j ≤n。

③循环阶段。根据递归关系式，确定Xi和Yj的LCS的长度，0≤i≤m。对于每个i循环，0≤j ≤n。

④根据二维数组b记录的信息以自底向上的方式来构造该LCS问题的最优解。

//基于DP动态规划求解LCS问题的伪代码如下：
LCS(X,Y)
  m = length(X)
  n = length(Y)
  FOR i = 1 TO m
    c[i][0] = 0
  FOR j = 1 TO n
    c[0][j] = 0
  FOR i = 1 TO m
    FOR j = 1 TO n
      IF X[i] == Y[j]
        c[i][j] = c[i-1][j-1] + 1
        b[i][j] = 1
      ELSE IF c[i-1][j] >= c[i][j-1]      //暗指x[i]!=y[j]  
        c[i][j] = c[i-1][j] 
        b[i][j] = 3
      ELSE
        c[i][j] = c[i][j-1] 
        b[i][j] = 2

//else if和else 就是在如果两个字母不匹配 当前位置的状态取左边或者上边的最大值
//对于第一个if 两个字母匹配 当前位置的状态取左斜对角位置+1；
//O(m+n+m*n) -> O(n的平方)

//构造LCS问题最优解的伪代码如下：
LCS-PRINT(b,X,i,j)
  IF i == 0 OR j == 0 
    RETURN
  IF b[i][j] == 1
    LCS-PRINT(b,X,i-1,j-1)
    PRINT X[i]
  ELSE IF b[i][j] == 3
    LCS-PRINT(b,X,i-1,j)
  ELSE
    LCS-PRINT(b,X,i,j-1) //b[i][j] == 2
//该算法的时复杂性为O(m+n)-> O(n)

LCS的其他解决方法：

穷举搜索法

枚举Xm={x1,x2,…,xm}的所有子序列，并逐一检查每个子序列是否也为Yn={y1,y2,…,yn}的子序列，其中最长的即为Xm和Yn的最长公共子序列。

该算法的时复杂性为O(n $2^m$ ) -> O(n $2^n$ )，指数级;

直接递归法

//直接递归是自顶向下的
LCS-REC(X,Y,i,j,c,b)
  IF i == 0 OR j == 0 
    RETURN 0
  IF X[i] == Y[j]
    PRINT X[i] 
    RETURN LCS-REC(X,Y,i-1,j-1,c,b) + 1 
  ELSE
    RETURN MAX(LCS-REC(X,Y,i-1,j,c,b),
                  LCS-REC(X,Y,i,j-1,c,b))

该算法的时复杂性为O(2 $2^{min(m,n))}$ ) -> O( $2^n$ )，指数级;

矩阵连乘

给定n个矩阵{A1, A2, A3, …, An}，其中Ai与Ai+1 (i=1,2,3, …,n-1)是可乘的。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的数乘次数最少。

穷举法

设n个矩阵连乘的不同计算次序数为P(n)。每种加括号方式都可分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)：

动态规划方法

性质：最优子结构性质--反证法；

计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的：

设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]；

当i=j，A[i:j]=A[i:i]。因此，m[i,i]=0，i=1,2,…,n；

当i<j，m[i,j] = m[i,k]+m[k+1,j]+ $p_{i-1}p_kp_j$ ， $A_i$ 维数为 $P_{i-1}$ x $P_i$ ；

//递归求解矩阵连乘问题的伪代码：
RECURSIVE-MATRIX-CHAIN(p,i,j,m,s)
  IF i == j
    m[i,j] = 0, s[i,j] = 0
	  RETURN
  m[i,j] = ∞
  FOR k = i TO j-1
    q = RECURSIVE-MATRIX-CHAIN(p,i,k,m,s)
      + RECURSIVE-MATRIX-CHAIN(p,k+1,j,m,s)
      + pi-1pkpj
      IF q < m[i,j]
      m[i,j] = q
      s[i,j] = k
  RETURN m AND s

//采用DP求解矩阵连乘问题的伪代码：
MATRIX-CHAIN-ORDER-DP(n,p,m,s) //p[1..n+1]为n个矩阵的维数
  //m[1..n, 1..n]为最优值，s[1..n, 1..n]为最优决策
  FOR i = 1 TO n
    m[i,i] = 0
  FOR l = 2 TO n //l为链的长度
    FOR i = 0 TO n-l+1
      j = i+l-1
      m[i,j] = ∞
      FOR k = i TO j-1
        q = m[i,k] + m[k+1,j] + pi-1pkpj
        IF q < m[i,j]
	        m[i,j] = q
          s[i,j] = k
  RETURN m AND s
//时间复杂度是n的三次方；

空间复杂度是O(1);

//采用DP求解矩阵连乘问题的伪代码：
MATRIX-CHAIN-ORDER-DP(n,p,m,s) //p[1..n+1]为n个矩阵的维数
  //m[1..n, 1..n]为最优值，s[1..n, 1..n]为最优决策
  FOR i = 1 TO n
    m[i,i] = 0
  FOR l = 2 TO n //l为链的长度
    FOR i = 0 TO n-l+1
      j = i+l-1
      m[i,j] = ∞
      FOR k = i TO j-1
        q = m[i,k] + m[k+1,j] + pi-1pkpj
        IF q < m[i,j]
	        m[i,j] = q
          s[i,j] = k
  RETURN m AND s
//时间复杂性 O(n) ;空间复杂性：O(n)


//主程序：
MATRIX-CHAIN-ORDER-DP-MAIN(p,n)
  //m[1..n, 1..n]为最优值，    
  //s[1..n, 1..n]为最优决策
  (m,s) = MATRIX-CHAIN-ORDER-DP(n,p,m,s)
  PRINT-OPTIMAL-PARENS(s,1,n)
// 时间复杂性：O(n3)  空间复杂性：O(n2)

算法设计与分析——矩阵连乘问题（动态规划） - 王陸 - 博客园 (cnblogs.com)

0-1背包问题

动态规划

n个物品和1个背包。对物品i，其价值为vi，重量为wi，背包容量为W。如何选取物品装入背包，使背包中所装入的物品的总价值最大？其中，wi, W都是正整数。

最优子结构性质：

设 (x1, x2,…, xn) 是所给0-1背包问题的一最优解，则 (x2,…, xn) 是下面相应子问题的一个最优解

//采用DP求解0-1背包问题的伪代码：
KNAPSACK-01-DP(w, v, W) //w为重量，v为价值，W为容量
  //C[1..n, 1..n]为最优值--最大价值
  FOR i = 1 TO n
    C[i,0] = 0
  FOR j = 1 TO W                   //可用容量
    C[0,j] = 0
  FOR i = 1 TO n
    FOR j = 1 TO W
      IF j < w[i]
        C[i,j] = C[i-1][j]         //装不下第i个物品
      ELSE
        C[i,j] = MAX{C[i-1][j],C[i-1][j-w[i]] + v[i]}   //在装下第i个物品和不装的价值最大判断 
  RETURN C 

//时间复杂度是O(nW) 空间复杂度O(1);

//0-1背包问题的最优解构建的伪代码：
KNAPSACK-TRACEBACK-01(w,W,C,X) //w为重量，W为容量，C为最优值
  //X[1..n]为构建的最优解 -- 选择哪个物品放进背包；
  n = w.length – 1
  j = W                              //可用容量
  FOR i = n TO 1
    IF C[i][j] == C[i-1][j]
      X[i] = 0                  //现在这个物品的价值和上一个一样就不放入 
    ELSE                          
      X[i] = 1                   //放入，可用容量减去当前物品重量；
      j -= w[i]
  RETURN X
//时间复杂度是O(n)  空间复杂度是O(1);

//主程序：
KNAPSACK-01-DP-MAIN(w,v,W) //w为重量，v为价值，W为容量
  KNAPSACK-01-DP(w,v,W,C)        --C存背包价值的最大化
      //X[1..n]为构建的最优解
  KNAPSACK-TRACEBACK(w,v,W,C,X)  --X存物品的有无
//时间复杂性：O(nW)。空间复杂性：O(nW)；

贪心算法

在不超过背包的容量的情况下，尽可能多（指重量，如全部或部分）地选择更为贵重（指单位重量的价值最大）的物品，直至装满背包为止。

//基于贪心法求解背包问题的伪代码如下：
GREEDY-KNAPSACK(w, v, W) //w为重量，v为价值，W为容量
  SORT-ASC-BY-V(v,w) //按照物品的单位价值非降序排序，同时调整v和w
  n = w.length
  //x[1..n]为最优值，存放已选物品的相应重量。各元素初始化为0
  wRemained = W           //剩余重量是W
  FOR i = 1 TO n          
    IF wRemained <= 0       //无剩余重量 
      BREAK;
    ELSE IF wRemained >= w[i]   
      x[i] = 1            //存入
      wRemained = W – w[i]
    ELSE
      x[i] = 0            //不存入
      BREAK
  RETURN x