1. 动态规划原理

动态规划（Dynamic Programming,DP）：通过把复杂的问题分解成更小的子问题，并存储这些子问题的解来避免计算重复子问题，从而达到降低计算复杂度的目的

两种分解的区别

区别分治策略动态规划
划分点通常只有一个划分点可以有多个划分点
子问题性质子问题之间都是相互独立的子问题是重叠的：一是存在重复的子问题，而是子问题的解依赖于其他子问题
如何处理子问题将子问题的解合并返回到上一级低级子问题的解被全局存储，以供更高级的子问题使用

动态规划的适用场景

  • 最优子结构：一个问题的最优解可以通过其子问题的最优解来构建
  • 重叠子问题：一个问题的子问题在解决过程中会被多次计算，并且不会生成新的子问题

考虑寻找一个图中从起点到终点的最长简单路径，假设图为A⇆B⇆C⇆D⇆AA \leftrightarrows B \leftrightarrows C \leftrightarrows D \leftrightarrows A，从A到D的最长简单路径是A←B←C←DA \leftarrow B \leftarrow C \leftarrow D，如果拆成两个子问题，A到B的最长简单路径是A←D←C←BA \leftarrow D \leftarrow C \leftarrow B，B到D的最长简单路径是B←A←DB \leftarrow A \leftarrow D，合并在一起就是A←D←C←B←A←DA \leftarrow D \leftarrow C \leftarrow B \leftarrow A \leftarrow D，显然这不是简单路径，不符合最优子结构！

动态规划的核心步骤

  1. 刻画一个最优子结构
  2. 递归地定义重叠子问题
  3. 采用自底向上的方法计算最优解的值
  4. 利用结果构造得到最优解的过程

刻画最优子结构的方式

  1. 证明求最优解的第一步总是做出一个选择
  2. 假定上述选择就是最优的
  3. 基于上述选择，确定划分为多少个子问题，以及每个子问题空间是什么
  4. 利用“剪切-粘贴”法，证明子问题的最优解与原问题的最优解是一致的

实现自底向上的方式

  • 只求解一次子问题：精心安排求解顺序，保证第一次求解某个子问题时就可以得到其最优解
  • 问题只依赖于其子问题：精心设计求解方程，保证所有依赖的子问题都已经求解完毕

2. 钢条切割

问题介绍

问题描述：有一根长度为n的钢条和一张价格表，目标是切割这根钢条使得销售这些片段可以获得最高收益（也可以不切割，一整根卖出去）

案例分析：假设有一根长度为4的钢条和如下的价格表，则有8种切割方案：<(4),(1,3),(2,2),(3,1),(1,1,2),(1,2,1),(2,1,1),(1,1,1,1)><(4),(1,3),(2,2),(3,1),(1,1,2),(1,2,1),(2,1,1),(1,1,1,1)>，其中(2,2)(2,2)的方案可以获得最高收益10

长度12345678910
价格1589101717202430

第1步：刻画一个最优子结构

对于当前钢条，考虑全部最佳切割点中最左边的切割点，该切割点将钢条分为左段和右段，可知左段不需要继续切割，右段需要继续切割（也可以不切割），因此当前钢条的最优收益 = 左段价格 + 右段的最佳收益

第2步：递归地定义重叠子问题

假设钢条总长为n，左段长度为i，最佳收益为r，钢条价格为p，则有

rn={0if n=0max⁡(pi+rn−i)if 0<i≤nr_n = \begin{cases} 0 & \text{if }n = 0 \\ \max(p_i + r_{n-i}) & \text{if }0 < i \leq n \end{cases}

第3步：采用自底向上的方法计算最优解的值

考虑每个长度l的钢条及其最大收益

  • 对于长为0的钢条，最大收益就是0
  • 对于长为1的钢条，最大收益就是价格
  • 对于长为2的钢条，最大收益可以分为左1加右1，左2加右0，其中长为0、1的最大收益由前面步骤可得
  • 对于长为3的钢条，最大收益可以分为左1加右2，左2加右1，左3加右0，其中长为0、1、2的最大收益由前面步骤可得
  • 对于长为4的钢条，最大收益可以分为左1加右3，左2加右2，左3加右1，左4加右0，其中长为0、1、2、3的最大收益由前面步骤可得
  • 以此类推，直到长为n，其中长为0、1、2、3、…、n-1的最大收益由前面步骤可得

第4步：利用结果构造得到最优解的过程

记录长为l的钢条对应的最佳切割点，相当于记录最佳切割点对应的左段长度，那么最优解 = 左段长度 + 右段钢条的左段长度 + 右段钢条的右段钢条的左段长度，以此类推，直到某次右段钢条的长度为0

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 从左到右输出每段长度
def optimal(left_len, n):
  left = 0
  right = n
  while right != 0:
    left = left_len[right]
    print(left)
    right = right - left

def cut_rod(p, n):
  # 最大收益
  reward = [0] * (n + 1)
  # 最佳切割点对应的左段长度
  left_len = [0] * (n + 1)
  # 每次循环得到长度为curlen的钢条的最大收益
  for cur_len in range(1, n + 1):
    # 初始化最大收益为负数，用于比较
    max_price = -1
    # 遍历所有切割点，i是左段长度，cur_len - i是右段长度
    for left in range(1, cur_len + 1):
      right = cur_len - left
      cur_price = p[left] + reward[right]
      # 更新最大收益和对应的切割点
      if cur_price > max_price:
        max_price = cur_price
        left_len[cur_len] = left
    # 记录cur_len的最大收益
    reward[cur_len] = max_price
  # 长度为n的最大收益
  max_price = reward[n]
  # 获取最优解的过程
  optimal(left_len, n)
  return max_price

3. 矩阵乘法链

问题介绍

问题描述：给定n个矩阵的乘法链，目标是找到一种结合顺序，使得计算矩阵乘法链所需要的标量乘法次数最小，其中p×qp \times q和q×rq \times r的矩阵相乘所需要的标量乘法次数为p⋅q⋅rp \cdot q \cdot r，得到的结果矩阵为p×rp \times r

案例分析：假设有三个矩阵A、B、C，它们的维度分别为10x100、100x5和5x50，有以下两种结合顺序，显然选择第1种的顺序所需的标量乘法次数更少

  1. (AB)C：需要10x100x5 + 10x5x50 = 7500次标量乘法
  2. A(BC)：需要10x100x50 + 100x5x50 = 75000次标量乘法

第1步：刻画一个最优子结构

对于当前矩阵乘法链，找到一个最佳切割点分成左链和右链，相当于给左链和右链都加上一个括号，则当前链的最小次数 = 左链的最小次数 + 右链的最小次数 + 两链结果相乘的次数

第2步：递归地定义重叠子问题

假设第i个矩阵的行值是p[i]p[i]，列值是p[i+1]p[i+1]，假设某条链的链首是第i个矩阵，链尾是第j个矩阵，该链的最小标量乘法次数表示为二维数组m[i][j]m[i][j]，对于切割点k，则有

m[i][j]=min⁡i≤k<j(m[i][k]+m[k+1][j]+p[i]⋅p[k+1]⋅p[j+1])m[i][j] = \min_{i \leq k < j} (m[i][k] + m[k+1][j] + p[i] \cdot p[k+1] \cdot p[j+1])

第3步：采用自底向上的方法计算最优解的值

考虑每个链长l以及对应的链首i和链尾j，有l=j−i+1l = j - i + 1

  • l=2，最小标量乘法次数就是p[i]⋅p[i+1]⋅p[i+2]p[i] \cdot p[i+1] \cdot p[i+2]
  • l=3，那么可以分解为左1乘右2，左2乘右1，其中长为2的由前面步骤可得
  • l=4，那么可以分解为左1乘右3，左2乘右2，左3乘右1，其中长为2、3的由前面步骤可得
  • l=5，那么可以分解为左1乘右4，左2乘右3，左3乘右2，左4乘右1，其中长为2、3、4的由前面步骤可得
  • 以此类推，直到l=n，其中长为1、2、3、…、n-1的由前面步骤可得

第4步：利用结果构造得到最优解的过程

需要额外的一个数组s[i][j]来保存该链对应的最佳切割点，那么最优解 = （最佳切割点） 和 （左链的最佳切割点）和 （右链的最佳切割点） 和 （左链-左链的最佳切割点和左链-右链的最佳切割点） 和 （右链-左链的最佳切割点和右链-右链的最佳切割点）和 …，以此类推，直到所有子链长度都是2即无法再分

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 递归求最优解
def optimal(s,i,j):
  if i == j:
    return 'A' + str(i)
  else:
    return '(' + optimal(s,i,s[i][j]) + 'x' + optimal(s,s[i][j]+1,j) + ')'

# 自底向上求最优解
def matrix_chain_order(p):
  # 矩阵个数即链的长度，-1是因为p多存了一个元素表示最后一个矩阵的列值
  n = len(p) - 1
  # 最小标量乘法次数
  m = [[0] * n for _ in range(n)]
  # 最佳切割点
  s = [[0] * n for _ in range(n)]
  # 每次循环得到长度为l的每个矩阵乘法链的最小标量乘法次数
  for l in range(2,n+1):
    # 遍历链首上标，根据公式l=j-i+1，且j最大为n-1，可知i最大为n-l
    for i in range(0,n-l+1):
      # 定义最小标量乘法次数为正无穷，用于比较
      min_mult = float('inf')
      # 计算链尾下标
      j = i + l - 1
      # 遍历每个切割点
      for k in range(i,j):
        # 左链
        left = m[i][k]
        # 右链
        right = m[k+1][j]
        # 当前最小标量乘法次数
        cur_mult = left + right + p[i]*p[k+1]*p[j+1]
        # 比较最小标量乘法次数
        if cur_mult < min_mult:
          min_mult = cur_mult
          s[i][j] = k
      # 得到长度为l的每个矩阵乘法链的最小标量乘法次数
      m[i][j] = min_mult
  # 最优解
  min_mult = m[0][n-1]
  res = optimal(s,0,n-1)
  return min_mult,res

m必须初始化为0，由于j=i+l-1，因此始终有j>i，所以要保证j<=i的矩阵值一直是0才能计算子问题的解

4. 最长公共子序列

问题介绍

问题描述：给定两个序列X和Y，目标是找到它们的最长公共子序列，其中子序列是指下标递增（不一定连续）的元素组成的序列，该问题又称为LCS问题（Longest Common Subsequence）

案例分析：假设X = ABDAB，Y = BCCDAACAB，它们的公共子序列有AB，BD，BDA，BDB，DAB，BDAB，其中最长的是BDAB，长度为4

第1步：刻画一个最优子结构

定理：对于X=<x1,x2,…,xm>X = <x_1,x_2,\ldots,x_m>和Y=<y1,y2,…,yn>Y = <y_1,y_2,\ldots,y_n>，它们之间任意一个LCS，记为Z=<z1,z2,…,zk>Z = <z_1,z_2,\ldots,z_k>，则有以下三种情况

  • 如果xm=ynx_m = y_n，则zk=xm=ynz_k = x_m = y_n，且Zk−1Z_{k-1}是Xm−1X_{m-1}和Yn−1Y{n-1}的LCS：只有zk=xm=ynz_k = x_m = y_n才能保证公共子序列是最大的，因此三个序列都减去这个元素同样满足LCS性质
  • 如果xm≠ynx_m \neq y_n，且zk≠xmz_k \neq x_m，则ZZ是Xm−1X_{m-1}和YY的LCS：XX减去一个与LCS毫不相干的元素，ZZ依旧保持LCS性质
  • 如果xm≠ynx_m \neq y_n，且zk≠ynz_k \neq y_n，则ZZ是XX和Yn−1Y_{n-1}的LCS：YY减去一个与LCS毫不相干的元素，ZZ依旧保持LCS性质

因此，问题可以分解为

  • 如果xm=ynx_m = y_n，则相当于求Xm−1X_{m-1}和Yn−1Y{n-1}的LCS
  • 如果xm≠ynx_m \neq y_n，则相当于求Xm−1X_{m-1}和YY的LCS和XX和Yn−1Y_{n-1}的LCS中的较长者

第2步：递归地定义重叠子问题

假设X=<x1,x2,…,xm>X = <x_1,x_2,\ldots,x_m>和Y=<y1,y2,…,yn>Y = <y_1,y_2,\ldots,y_n>，令c[i,j]c[i,j]表示XiX_i和YjY_j的LCS的长度，则有

c[i,j]={0if i=0 or j=0c[i−1,j−1]+1if i,j>0 and xi=yjmax⁡(c[i,j−1],c[i−1,j])if i,j>0 and xi≠yjc[i,j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ c[i-1,j-1] + 1 & \text{if } i,j > 0 \text{ and } x_i = y_j \\ \max(c[i,j-1],c[i-1,j]) & \text{if } i,j > 0 \text{ and } x_i \neq y_j \end{cases}

第3步：采用自底向上的方法计算最优解的值

考虑每个长度下的X和每个长度下的Y对应的c[i][j]

  • 如果X或Y当前长为0，则对应的LCS都是0
  • X最长为1
    • Y最长为1：LCS(1,1)的长度取决于LCS(0,1)，LCS(1,0)，LCS(0,0)，而这三个都在之前得到
    • Y最长为2：LCS(1,2)的长度取决于LCS(0,2)，LCS(1,1)，LCS(0,1)，而LCS(1,1)在之前已经得到
    • 以此类推，直到Y最长为n
  • X最长为2
    • Y最长为1：LCS(2,1)的长度取决于LCS(1,1)，LCS(2,0)，LCS(1,0)，而LCS(1,1)在之前已经得到
    • Y最长为2：LCS(2,2)的长度取决于LCS(1,2)，LCS(2,1)，LCS(1,1)，而LCS(2,1)在之前已经得到
    • 以此类推，直到Y最长为n
  • 以此类推，直到X最长为m

第4步：利用结果构造得到最优解的过程

由定理可知，只有同时改变X和Y，即当xm=ynx_m = y_n时，才会在LCS中加入元素xmx_m，其他情况下都是单独改变X或单独改变Y去寻找xm=ynx_m = y_n的情况，所以一个二维数组记录每次情况

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 递归找最大公共子序列
def optimal(road, X, len_X, len_Y):
  if len_X == 0 or len_Y == 0:
    return ''
  # 从右下往左上遍历，因此新找到的元素要放在最后面
  if road[len_X][len_Y] == 'bingo':
    return optimal(road, X, len_X - 1, len_Y - 1) + X[len_X]
  elif road[len_X][len_Y] == 'left':
    return optimal(road, X, len_X, len_Y - 1)
  elif road[len_X][len_Y] == 'up':
    return optimal(road, X, len_X - 1, len_Y)

def LCS(X, Y):
  # 在X和Y的开头插入'$'，以匹配下标和序号
  X = '$' + X
  Y = '$' + Y
  len_X = len(X)
  len_Y = len(Y)
  common = [[0 for _ in range(len_Y)] for _ in range(len_X)]
  road = [['' for _ in range(len_Y)] for _ in range(len_X)]
  for i in range(1, len_X):
    for j in range(1, len_Y):
      if X[i] == Y[j]:
        common[i][j] = common[i - 1][j - 1] + 1
        road[i][j] = 'bingo'
      else:
        # 去掉当前X的最后一个元素得到的LCS
        X_left = common[i][j - 1]
        # 去掉当前Y的最后一个元素得到的LCS
        Y_up = common[i - 1][j]
        if X_left > Y_up:
          common[i][j] = X_left
          road[i][j] = 'left'
        else:
          common[i][j] = Y_up
          road[i][j] = 'up'
  res = optimal(road, X, len_X - 1, len_Y - 1)
  return common, res

5. 最优二叉搜索树

问题介绍

问题描述：给定n个关键字<k1,k2,k3,…,kn><k_1,k_2,k_3,\ldots,k_n>，其中还存在n+1个伪关键字<d0,d1,d2,…,dn><d_0,d_1,d_2,\ldots,d_n>，满足dn>kn, ki<di<ki+1d_n>k_n,\,k_i<d_i<k_{i+1}，关键字没找到就会找到伪关键字，每个关键字有一个访问概率p，每个伪关键字也有一个访问概率q，假定搜索代价是找到关键字所访问的结点个数，即depth(i)+1depth(i)+1，要求构造出一个二叉搜索树，使得在该树中的搜索各种关键字的代价最小，即：1+∑i=1ndepth(ki)×pi+∑i=0ndepth(di)×qi1 + \sum_{i=1}^{n}{depth(k_i) \times p_i} + \sum_{i=0}^{n}{depth(d_i) \times q_i}最小，也称为OBST问题（Optimal Binary Search Tree）

案例分析：对一个n=5的关键字集合及如下搜索概率，有以下两种树结构，其中第二种代价最小为2.75

i012345
p_i0.000.150.100.050.100.20
q_i0.050.100.050.050.050.10


最优二叉搜索树不一定是高度最矮的，搜索频率越大的也不一定出现在越上面

第1步：刻画一个最优子结构

如果一颗树是最优二叉搜索树，则它的根节点的左子树和右子树也都是最优二叉搜索树

第2步：递归地定义重叠子问题

假设当前树存在按序关键字<ki,ki+1,…,kj><k_i,k_{i+1},\ldots,k_j>，其中选取kr,i≤r≤jk_r,i\leq r \leq j作为根结点，那么它的左子树就只有关键字<ki,…,kr−1><k_i,\ldots,k_{r-1}>和伪关键字<di−1,…,dr−1><d_{i-1},\ldots,d_{r-1}>，右子树就只有关键字<kr+1,…,kj><k_{r+1},\ldots,k_j>和伪关键字<dr,…,dj><d_r,\ldots,d_j>

但子树的搜索代价是以其高度计算的，将子树插到原树的根节点的位置会导致高度增加1，因此需要计算子树插入原树导致的搜索代价增量，即w[i][j]=1×(∑l=ijpl+∑l=i−1jql)w[i][j]= 1 \times (\sum_{l=i}^{j}{p_l} + \sum_{l=i-1}^{j}{q_l})，它也满足递归式w[i][j]=w[i][r−1]+w[r+1,j]+1×prw[i][j] = w[i][r-1] + w[r+1,j] + 1 \times p_r

令e[i][j]表示以关键字<ki,…,kj><k_i,\ldots,k_j>和伪关键字<di−1,…,dj><d_{i-1},\ldots,d_j>组成的最优二叉搜索树的搜索代价则有：

e[i][j]={qiif i>jmin⁡i≤r≤j{e[i][r−1]+e[r+1][j]+w[i][j]}if i≤je[i][j] = \begin {cases} q_i & \text{if } i > j \\ \min_{i\leq r \leq j} \{e[i][r-1] + e[r+1][j] + w[i][j]\} & \text{if } i \leq j \end{cases}

第3步：采用自底向上的方法计算最优解的值

考虑每个子树的关键字的起始下标是i，终止下标是j，则结点总数为l = j - i + 1

  • l=0，就是伪关键字，搜索代价为q[i-1]
  • l=1，r只能是i（左0右0）
  • l=2，r可以是i（左0右1），i+1（左1右0），其中结点总数为0、1的在之前已经算出
  • l=3，r可以是i（左0右2），i+1（左1右1），i+2（左2右0），其中结点总数为0、1、2的在之前已经算出
  • 以此类推，直到l=n，其中长为0、1、2、3、…、n-1的在之前已经算出

第4步：利用结果构造得到最优解的过程

用一个二维数组root[i][j]记录划分子树选取的最佳根节点，那么从root[1][n]选取的划分根节点开始划分成左子树和右子树，然后再选取左子树的划分根节点和右子树的划分根节点，以此类推，直到无法划分

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 先序遍历最优搜索二叉树
def optimal(root, i, j):
  if i == j + 1:
    print('d_' + str(j))
    return
  r = root[i][j]
  print('k_' + str(r))
  optimal(root, i, r-1)
  optimal(root, r+1, j)

def OBST(p,q):
  # p的下标从1开始，q的下标从0开始，但是他们最后一个下标都是n，因此在p的最前面加一个元素
  p = [0.0] + p
  length = len(q)
  w = [[0.0 for _ in range(length)] for _ in range(length)]
  e = [[0.0 for _ in range(length)] for _ in range(length)]
  root = [[0 for _ in range(length)] for _ in range(length)]
  # 由于l = j - i + 1，l = 0时，j = i - 1
  for i in range(1, length):
    e[i][i-1] = q[i-1]
    w[i][i-1] = q[i-1]
  for l in range(1, length):
    # j最大为length-1，根据公式l=j-i+1，因此i最大为length-l
    for i in range(1, length - l + 1):
      # 根据公式l=j-i+1,因此j=i+l-1
      j = i + l - 1
      e[i][j] = float('inf')
      w[i][j] = w[i][j-1] + p[j] + q[j]
      for r in range(i, j+1):
        if r + 1 > j:
          min_e = e[i][r-1] + q[j] + w[i][j]
        else:
          min_e = e[i][r-1] + e[r+1][j] + w[i][j]
        if min_e < e[i][j]:
          e[i][j] = min_e
          root[i][j] = r
  # 最优解
  optimal(root, 1, 5)
  min_e = e[1][length-1]
  return min_e

6.