《算法导论》:动态规划学习笔记

灰太狼 2023-07-10 15:58 3阅读 0赞

> 参考资料：《算法导论》

### 动态规划方法 ###

动态规划方法用于解决这样一类问题:

*  问题具有最优子结构性质，即如果这个问题达到了最优解，那么此时构成它的子问题也应当是最优解, 这与贪心算法类似
 *  子问题空间应该足够"小", 即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题
 *  可能需要尝试不同的划分方法，将问题分解成不同的子问题，以求得全局最优解

一般求解步骤:

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

## 问题求解 ##

这里记录了书上提到的三个例子

*  钢条切割问题展示了动态规划中等价的两种实现
    
     *  带备忘的自顶向下
     *  自底向上
 *  矩阵链乘法和最长公共子序列展示了动态规划问题的一般分析方法

### 1.钢条切割问题 ###

一个长度为n的钢条，n为整数，切割为多个长度仍为整数的子钢条，每种长度的钢条价格不一，有一个记录每种长度的钢条价格的价格表p, 求最优切割方案  
由条件可以推导出以下结论

*  如果长度为n的钢条价格足够高，则无需切割
 *  共有 2 n − 1 2^\{n-1\} 2n−1种不同的切割方案，切割数目m从0到n，每种数目对应 C n − 1 m C\_\{n-1\}^m Cn−1m种方法，求和得 2 n − 1 2^\{n-1\} 2n−1

#### 递归实现 ####

**思路**: 将钢条在下标 i i i处分为左右两部分，(因为总会有一个分割点，不切割的话 i i i=0) ，那么可以只对右边长度为 n − i n-i n−i的部分进行递归处理，若用 f ( n ) f(n) f(n)表示长度为 n n n的钢条的最佳切割方案，则有:  
 f ( n ) = m a x ( p i + f ( n − i ) ) 0 < = i < = n f(n) = max(p\_i+f(n-i)) \_\{0<=i<=n\} f(n)=max(pi\+f(n−i))0<=i<=n  
**时间复杂度**: 由于有 2 n − 1 2^\{n-1\} 2n−1种分法，递归的解法实际上尝试了所有的分法，所以时间复杂度:  O ( 2 n − 1 ) O(2^\{n-1\}) O(2n−1)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70]

**分析**: 递归的解法之所以慢，是因为在递归时重复求解了子问题，如果使用一个表记录子问题的结果，就可以提升求解效率

#### 动态规划方法实现 ####

1.自顶向下  
数组r保存了从0到n每个长度的最优方案，以确保不会重复计算。本例中这种方法分析起来不如自底向上清晰

MEMOIZED-CUT-ROD(p,n)
    let r[0...n] be a new array
    for i=0 to n:
    	r[i] = INT_MIN
    return MEMOIZED-CUT-ROD-AUX(p,n,r)
    
    MEMOIZED-CUT-ROD-AUX(p,n,r)
    if r[n] >= 0:
    	return r[n]
    if n == 0:
    	q = 0
    else:
    	q = MIN
    	for i=1 to n:
    		q = max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))
    r[n]=q
    return q

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 1]  
2.自底向上  
自底向上方法同样使用数组r保存从0到n每个长度的最优方案，思路是一样的，但是结构更清晰，上一个方法由于使用了递归，分析起来比较麻烦。

BOTTOM-UP-CUT-ROD(p, n)
    let r[0...n] be a new array
    r[0]=0
    for j=1 to n:
    	q = MIN
    	for i=1 to j:
    		q=max(q,p[i]+r[j-i])
    	r[j]=q
    return r[n]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 2]

### 2.矩阵链乘法 ###

![在这里插入图片描述][20200305092435415.png]

##### 步骤1: 最优方案的结构特征 #####

一个 m ∗ n m\*n m∗n的矩阵和一个 n ∗ k n\*k n∗k的矩阵相乘，需要进行 m n k mnk mnk次乘法运算  
假设存在最优划分点k, 那么k的左右两边都是最优划分的

##### 步骤2: 递归求解方案 #####

若用 m \[ i , j \] m\[i, j\] m\[i,j\]表示计算 A i . . . A j A\_i...A\_j Ai...Aj的最优解，那么在 i i i与 j j j范围内寻找一个k, 假设这个k是计算 A i . . . A j A\_i...A\_j Ai...Aj的最优划分，那么就把问题再次分解成了更小的子问题，且存在下面的递推关系，使用自底向上就可以完成求解  
![在这里插入图片描述][20200305094414306.png]

##### 步骤3: 计算最优代价 #####

输入是一个序列  p = < p 0 , p 1 , p 2 , . . . , p n > p=<p\_0,p\_1,p\_2,...,p\_n > p=<p0,p1,p2,...,pn>  
使用辅助表  m \[ 1... n , 1... n \] m\[1...n,1...n\] m\[1...n,1...n\] 保存代价  m \[ i , j \] m\[i,j\] m\[i,j\]  
另一个辅助表  s \[ 1... n − 1 , 2... n \] s\[1...n-1,2...n\] s\[1...n−1,2...n\] 记录最优值 m \[ i , j \] m\[i,j\] m\[i,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:
    	m[i,i] = 0   // 当长度为0时代价为0
    for l = 2 to n:  // l是子链的长度
    	for i = 1 to n-l+1:
    		j = i + l -1
    		m[i,j] = MAX
    		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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 3]

从长度为1、2的子链代价开始计算，逐步推导出完整的代价辅助表m

##### 步骤4: 构造最优解 #####

PRINT-OPTIMAL-PARENS(s, i , j)
    if i==j:
    	print "A[i]"
    else:
    	print "("
    	PRINT-OPTIMAL-PARENS(s, i, s[i,j])
    	PRINT-OPTIMAL-PARENS(s, s[i,j]+1,j)
    	print ")"

### 3.最长公共子序列 ###

*  子序列: 从原序列的下标集合中选取一部分递增的下标序列，以此构建的子序列
 *  公共子序列: X和Y存在相同的子序列Z
 *  注意点: 这里的子序列**未必**是原序列中**连续**的一部分

![在这里插入图片描述][20200305114836445.png]

##### 步骤1:最长公共子序列特征刻画 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 4]

##### 步骤2:递归解 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 5]

##### 步骤3: 计算LCS长度 #####

LCS-LENGTH(X, Y)
    m = X.length
    n = Y.length
    let b[1...m,1...n] and c[0...m,0...n] be new tables
    for i = 1 to m:
    	c[i, 0] = 0
    for j = 1 to n:
    	c[0,j] = 0
    for i = 1 to n:
    	for j = 1 to m:
    		if x[i] == y[j]:
    			c[i,j] = c[i-1,j-1] + 1
    			b[i,j] = "\"
    		elseif c[i-1,j] >= c[i, j-1]:
    			c[i,j] = c[i-1,j]
    			b[i,j] = "|"
    		else:
    			c[i,j] = c[i,j-1]
    			b[i,j] = "--"
    return c, b

b 的作用是辅助打印出LCS

##### 步骤4: 构造LCS #####

PRINT-LCS(b,X,i,j)
    if i==0 or j==0:
    	return None
    if b[i, j] == "\":
    	PRINT-LCS(b,X,i-1,j-1)
    	print x[i]
    elseif b[i,j] == "|":
    	PRINT-LCS(b,X,i-1,j)
    else:
    	PRINT-LCS(b,X,i,j-1)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303213104659.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200303220936718.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200303220911258.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1,size_16,color_FFFFFF,t_70
[20200305092435415.png]: https://img-blog.csdnimg.cn/20200305092435415.png
[20200305094414306.png]: https://img-blog.csdnimg.cn/20200305094414306.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200305101508877.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1,size_16,color_FFFFFF,t_70
[20200305114836445.png]: https://img-blog.csdnimg.cn/20200305114836445.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200311215757785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020031121585361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzQxNzQzMTk1,size_16,color_FFFFFF,t_70