动态规划方法通常用来求解最优化问题（optimization problem）。

我们通常按如下4个步骤来设计一个动态规划算法：

动态规划算法求解问题的基础。

刻画一个最优解的结构特征
递归地定义最优解的值
计算最优解的值，通常采用自底向上的方法

维护一些额外信息，以便用来构造一个最优解

利用计算出的信息构造一个最优解

15.1 钢条切割

研究如何将长钢条切割成短钢条，使得总价值最高

钢条切割问题

给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,……,n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢铁的价格pn足够大，最优解可能就是完全不需要切割。

最优子结构性质

问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

伪代码自顶向下递归实现

//p：价格数组
//n：整数
//返回值：长度为n的钢条的最大收益
CUT-ROD(p,n)
  if n == 0
    return 0
  q = -∞//将最大收益q初始化为-∞
  for i = 1 to n
    q = max(q,p[i] + CUT-ROD(p,n-1))
  return q//返回计算结果

伪代码带备忘的自顶向下法动态规划

//p：价格数组
//n：整数
//返回值：长度为n的钢条的最大收益
MEMOIZED-CUT-ROD(p,n)
  let r[0……n] be a new array
  for i = 0 to n
    r[i]= -∞
  return MEMOIZED-CUT-ROD-AUX(p,n,r)

MEMOIZED-CUT-ROD-AUX(p,n,r)
  if r[n] ≥ 0//检查所需值是否已知
    return r[n]//如果是，则直接返回保存的值
    //用通常方法计算所需值q【14-18】
  if n == 0
    q = 0
  else q = - ∞
    for i = 1 to n
      q = max(q,p[i] + MEMOIZED-CUT-ROD-AUX(p,n-i,r))
  r[n] = q//将q存入r[n]
  return q//将q返回

伪代码自底向上法动态规划

BOTTOM-UP-CUT-ROD(p,n)
  let r[0……n] be a new array//创建一个新数组r[0……n]来保存子问题的解
  r[0] = 0//将r[0]初始化为0，因为长度为0的钢条没有收益
  //[5-8]对j=1,2,……,n按升序求解每个规模为j的子问题，求解规模为j的子问题的方法与CUT-ROD所采用的方法相同
  for j = 1 to n
    q = -∞
    for i = 1 to j
      q = max (q,p[i] + r[j-i])//现在直接访问数组元素r[j-i]来获得规模为j-i的子问题的解，而不必进行递归调用
    r[j]=q//将规模为j的子问题的解存入r[j]
  return r[n]//返回r[n]，即最优解rn

15.1-3

alt

// n：钢条长度
// p：价格表p[1……n]
// c：切割成本
//返回值：长度为n的钢条的最大收益
BOTTOM-TOP-CUT-ROD(p,c,n)
  create a new array r[0……n]
  r[0] = 0
  for i = 1 to n
    q= p[i]
    for j = i - 1 to 1
      q = max(q,p[j] + r[i-j] - c)
    r[i] = q
  return r[n]

15.1-5

alt

//n：斐波那契数列的元素的索引号
//返回值：第n个斐波那契数列的值
FIBONACII(n)
  if n < 2
    return 1
  else 
    f1 = 1
    f2 = 1
    for i = 2 to n
      q = f1 + f2
      f2 = f1
      f1 = q
    return q

该算法的核心是从2到n的循环迭代，这反映了自下而上的求解方法。

每次迭代 i，只需要用到前两个元素，即第 i-1 个元素和第 i-2 个元素。

因此，仅需要用两个局部变量f1和f2来保存第 i-1 个元素和第 i-2 个元素，

并且每次迭代后更新这两个局部变量，而无需保存从0到 n 的每个元素。

显然，这个算法的时间复杂度为O(n)。

alt

15.2 矩阵链乘法

解决如何用最少的标量乘法操作完成一个矩阵链相乘的运算

伪代码两个矩阵相乘的标准算法

//rows：矩阵的行数
//columns：矩阵的列数
MATRIX-MULTIPLY(A,B)
  if A.columns ≠ B.rows
    errror "incompatible dimensions【不相容维数】"
  else let C be a new A.rows × B.columns matrix
    for i = 1 to A.rows
      for j = 1 to B.columns
        c[ij] = 0
        for k = 1 to A.columns
          c[ij] = c[ij] + a[ik] · b[kj]
  return C

两个矩阵A和B只有相容【compatible】，即A的列数等于B的行数时才能相乘。

如果A是p×q的矩阵，B是q×r的矩阵，那么乘积C是p×r的矩阵。

计算C所需时间由第11行的标量乘法的次数决定，即pqr。

矩阵链乘法问题

给定n个矩阵的链<A1,A2,……An>，矩阵Ai的规模为p^(i-1)×pi(1 ≤ i ≤ n)，求完全括号化方法，使得计算乘积A1A2……An所需标量乘法次数最少

步骤1：最优括号化方案的结构特征

步骤2：一个递归求解方案

步骤3：计算最优代价

伪代码

//矩阵Ai的规模为p^(i-1)×p^(i)(i=1,2,……,n)
//序列p=<p0,p1,……,pn>
//m[i,j]表示计算矩阵A[i,j]所需标量乘法次数的最小值
//s[i,j]保存A[i]A[i+1]...A[j]最优括号化方案的分割点位置k，即使得m[i,j]=m[i,k]+m[k+1,j]+p[i-1]p[k]p[j]成立的k值
MATRIX-CHAIN-ORDER(p)
//求出了计算矩阵链乘积所需的最少标量乘法运算次数
//但并未直接指出如何进行这种最优代价的矩阵链乘法计算
  n = p.length - 1
  let m[1……n,1……n] and s[1……n-1,2……n] be new tables
  for i = 1 to n//对所有i=1,2,……,n计算
    m[i,i] = 0 // 长度为1的链的最小计算代价
  for l= 2 to n // l is the chain length
    j = i + l - 1
    m[i,j] = ∞
    for k = i to j-1
    q = m[i,k] + m[k+1,j] + p[i-1]p[k]p[j]
    if q < m[i,j]
      m[i,j] = q
      s[i,j] = k
  return m and s

执行算法的过程

alt alt

步骤4：构造最优解

伪代码最优括号化方案

//s i j：MATRIX-CHAIN-ORDER得到的表s及下标i和j
//调用PRINT-OPTIMAL-PARENS(s,1,n)即可输出<A1,A2,……,An>的最优括号化方案
PRINT-OPTIMAL-PARENS(s,i,j)
  if i == j
    print "A"
  else print "("
    PRINT-OPTIMAL-PARENS(s,i,s[i,j])
    PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)
    print ")"

15.2-1

alt

最优括号化方案为（（A1A2）（（A3A4）（A5A6））），所需要的标量乘法的次数为2010

验证 python代码

def MATRIX_CHAIN_ORDER(p):
    n = len(p)
    s = [[0 for j in range(n)] for i in range(n)]
    m = [[0 for j in range(n)] for i in range(n)]
    for l in range(2, n):  # l is the chain length
        for i in range(1, n - l + 1):
            j = i + l - 1
            m[i][j] = 1e9
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k
    print()
    PRINT_OPTIMAL_PARENS(s, 1, n - 1)
    print()

def PRINT_OPTIMAL_PARENS(s, i, j):
    if i == j:
        print('A', end='')
        print(i, end='')
    else:
        print('(', end='')
        PRINT_OPTIMAL_PARENS(s, i, s[i][j])
        PRINT_OPTIMAL_PARENS(s, s[i][j] + 1, j)
        print(')', end='')

A = [5, 10, 3, 12, 5, 50, 6]
MATRIX_CHAIN_ORDER(A)

15.4 最长公共子序列

展示如何用动态规划方法找到两个序列的最长公共子序列

子序列

alt alt

公共子序列

alt

最长公共子序列问题

alt

步骤1：刻画最长公共子序列的特征

定理 15.1 LCS的最优子结构

alt alt

步骤2：一个递归解

alt

公式 15.9

alt

步骤3：计算LCS的长度

步骤4：构造LCS

15.4-5

alt

Solution

给出一个数字列表L，复制一个名为L'的L，然后对L'进行排序

伪代码过程 PRINT-LCS(c, X, Y)

PRINT-LCS(c, X, Y)
    n = c[X.length, Y.length]
    let s[1..n] be a new array
    i = X.length
    j = Y.length
    while i > 0 and j > 0
        if x[i] == y[j]
            s[n] = x[i]
            n = n - 1
            i = i - 1
            j = j - 1
        else if c[i - 1, j] ≥ c[i, j - 1]
            i = i - 1
        else j = j - 1
    for i = 1 to s.length
        print s[i]

伪代码过程 MEMO-LCS-LENGTH-AUX(X, Y, c, b)

MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    m = |X|
    n = |Y|
    if c[m, n] != 0 or m == 0 or n == 0
        return
    if x[m] == y[n]
        b[m, n] = ↖
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y[1..n - 1], c, b) + 1
    else if MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) ≥ MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
        b[m, n] = ↑
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b)
    else
        b[m, n] = ←
        c[m, n] = MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)

伪代码过程 MEMO-LCS-LENGTH(X, Y)

MEMO-LCS-LENGTH(X, Y)
    let c[1..|X|, 1..|Y|] and b[1..|X|, 1..|Y|] be new tables
    MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    return c and b

然后，在这两个列表上运行theLCS算法。最长的公共子序列必须是单调递增的，因为它是L'的一个子序列，已排序。它也是最长的单调递增子序列，因为作为L'的子序列只会增加子序列必须是单调递增的限制。自从∣L∣=∣L′∣=n、排序L可以在o（n^2）时间内完成，最终运行时间为o（|L||L’|）=o（n^2）。

15.4-6

Give an O(nlgn)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers. Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of lengthi−1. Maintain candidate subsequences by linking them through the input sequence.)

给出了求n个数序列的最长单调递增子序列的O（nlgn）-时间算法。提示：注意长度为i的候选子序列的最后一个元素至少与长度为i的候选子序列的最后一个元素一样大−1.通过输入序列链接候选子序列来维护候选子序列。）

Solution

LONG-MONOTONIC（A）算法返回A的最长单调递增子序列，其中A的长度为n。

该算法的工作原理如下：将创建一个新数组B，使得B[i]包含长度为ii的最长单调递增子序列的最后一个值。一个新的数组C将是这样的，即C[i]包含长度ii的单调递增子序列，其中最后一个元素最小。

要分析运行时间，请注意B的条目是按排序顺序排列的，因此我们可以在O（lgn）时间内执行第9行。由于for循环中的每一行占用固定时间，因此总运行时间为O（nlgn）。

伪代码过程 LONG-MONOTONIC(A)

LONG-MONOTONIC(A)
    let B[1..n] be a new array where every value = ∞
    let C[1..n] be a new array
    L = 1
    for i = 1 to n
        if A[i] < B[1]
            B[1] = A[i]
            C[1].head.key = A[i]
        else
            let j be the largest index of B such that B[j] < A[i]
            B[j + 1] = A[i]
            C[j + 1] = C[j]
            INSERT(C[j + 1], A[i])
            if j + 1 > L
                L = L + 1
    print C[L]

第15章 动态规划

15.1 钢条切割

钢条切割问题

最优子结构性质

伪代码 自顶向下递归实现

伪代码 带备忘的自顶向下法动态规划

伪代码 自底向上法动态规划

15.1-3

15.1-5

15.2 矩阵链乘法

伪代码 两个矩阵相乘的标准算法

矩阵链乘法问题

步骤1：最优括号化方案的结构特征

步骤2：一个递归求解方案

步骤3：计算最优代价

伪代码

执行算法的过程

步骤4：构造最优解

伪代码 最优括号化方案

15.2-1

验证 python代码

15.4 最长公共子序列

子序列

公共子序列

最长公共子序列问题

步骤1：刻画最长公共子序列的特征

定理 15.1 LCS的最优子结构

步骤2：一个递归解

公式 15.9

步骤3：计算LCS的长度

步骤4：构造LCS

15.4-5

Solution

伪代码 过程 PRINT-LCS(c, X, Y)

伪代码 过程 MEMO-LCS-LENGTH-AUX(X, Y, c, b)

伪代码 过程 MEMO-LCS-LENGTH(X, Y)

15.4-6

Solution

伪代码 过程 LONG-MONOTONIC(A)

第15章动态规划

伪代码自顶向下递归实现

伪代码带备忘的自顶向下法动态规划

伪代码自底向上法动态规划

伪代码两个矩阵相乘的标准算法

伪代码最优括号化方案

伪代码过程 PRINT-LCS(c, X, Y)

伪代码过程 MEMO-LCS-LENGTH-AUX(X, Y, c, b)

伪代码过程 MEMO-LCS-LENGTH(X, Y)

伪代码过程 LONG-MONOTONIC(A)