动态规划 - 贪心算法

northboat 1/12/2023 Algorithm

动态规划

Dynamic programming：使多阶段决策过程最优的通用方法

动态规划不仅是应用数学中用来解决某类优化问题的重要工具，而且在计算机领域被当作一种通用的算法设计技术

总体思想：分治思想

将待求解问题分解成若干个子问题，如果分解得到的子问题重复出现，可用表格将已计算出的结果保存以节省重复计算，从而降低时间复杂度
动态规划适用于解决包含重叠子问题的优化问题
重叠子问题一般出现在对给定问题求解的递归关系中，递归关系包含了更小子问题的解

动态规划基本步骤

分析问题最优解的结构，找出最优解的性质
递归地定义最优解的代价
以自底向上的方式计算出最优解的代价并保存
根据计算最优解的代价信息构造最优解

基本要素：最优子结构和重叠子问题

最优子结构，如果一个问题的最优解包含了它的子问题的最优解，则称此问题具有最优子结构

即该问题的最优解同时是其子问题的最优解

重叠子问题，递归算法中求解子问题，若重复求解同一子问题，则称该问题存在重叠子问题

备忘录方法，对子问题的求解结果进行保存，每向下求一步，保存一次，是自顶向下的；而动态规划不是，动态规划是自底向上的

应用范例：矩阵连乘问题，最长公共子序列，背包问题，最优二叉搜索树问题

矩阵连乘

将一个矩阵连乘不断分割，找到乘法次数最少的排列

p[]数组记录矩阵阶数；m[i][j]数组记录从矩阵i乘到矩阵j的乘法次数；s[i][j]数组记录m[i][j]的分割位置 k

矩阵连乘问题，对于pxq乘以qxr的矩阵乘法，将得到一个pxr的结果矩阵，结果矩阵的每个元素需要q个元素相乘并相加，即共执行prq次乘法

T(n) = T(pqr)

在连乘时，不同的乘法次序将得到不同的新矩阵，从而总复杂度有多有少，如何找到复杂度最小的连乘

void MatrixChain(int p[], int n, int m[][] ,int s[][]) {
    for(int i = 1; i <= n; i++) {
        m[i][i]=0; //最小的子问题，连乘矩阵个数为1
    }
    for(int r = 2; r <= n; r++) { //r代表连乘的矩阵个数，从2到n
        for(int i = 1; i <= n-r+1; i++) {  //枚举左边界
            // 确定右边界
            int j = i+r-1;
            // 将矩阵分为 m[i:i] 和 m[i+1, j] 作为本轮初始分割
            m[i][j] = m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; // m[i][i] == 0
            // 记录第几轮
            s[i][j] = i;
            for(int k = i+1; k < j; k++) {  // 讨论k的所有可能情况
                int t = m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];
                if(t < m[i][j]) {
                    m[i][j]=t;
                    s[i][j]=k; // 选择数乘次数最小的情况，并将相关数据覆盖于表中的相应位置
                }
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

举个栗子

p 表比矩阵数大一轮，第三个矩阵的行数实际上就是第二个矩阵的列数，于是我们只需要存每个矩阵的行数，然后单独存最后一个矩阵的列数

在计算时，严格根据子问题的大小逐级提升

先确定m[i:i]，均为 0
再算长度为 2 的子问题，如m[1:2], m[2,3]，这一步很好算，因为只有一种分割方法，其值实际上就等于m[i:j] = p[i-1]p[i][j]，因为k = i
再计算长度为 3 的序列，这里就有两种分割方法，如m[2,4] = m[2:2] + m[3:4]和m[2,4] = m[2:3] + m[4:4]，需要一一计算比对赋予m[2:4]最小的一个值

这个 s 表实际上记录的是子问题m[i,j]最佳的分割点，如s[1,6] = 3，就表示矩阵连乘问题m[1:6]的最佳分割点k = 3，该问题可被最佳分解为m[1,3]和m[4,6]

根据这个 s 表，我们可以输出得到最佳的连乘序列

void print_optimal_parens(int s[], int i, int j){
    // i j 分别表示左右边界
    if(i == j){
        cout << 'A' << i << ' ';
    }
    cout << '(';
    print_optimal_parens(s, i, s[i][j]);
    print_optimal_parens(s, s[i][j]+1, j);
    cout << ')';
}

1
2
3
4
5
6
7
8
9
10

最长公共子序列

longest common subsequence，LCS

求两个数组最长公共子序列的长度，注意子序列的定义：对于序列[a,b,c,d,e]，[a,c,e]是其子序列，因为顺序没有发生改变

递归定义

在实际求解时，先将“边框”全部置零，然后一点点向右下方遍历求解，

在遍历过程中，可以记录移动的方向，如xi = yi时，说明向右下方移动，c[i,j-1] > c[i-1,j]时说明向下方移动

lcs-length(X, Y){
	m = length[X]
	n = length[Y]
    for i = 1 to m // 初始化“边框”
		c[i, 0] ← 0
	for j = 0 to n
		c[0, j] ← 0
 	for i = 1 to m
		for j = 1 to n
			if xi == yj
 				c[i, j] = c[i − 1, j − 1] + 1
 				b[i, j] = "↖"
 			else if 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 and b
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

根据返回的 b 数组，构造最优解（最长公共子序列）

print-lcs(b, X, i, j)
	if i = 0 or j = 0
		return
	if b[i, j] = '↖'
		print-lcs(b, X, i − 1, j − 1)
		print xi
	else if b[i, j] = '↑'
		print-lcs(b, X, i − 1, j)
	else if b[i, j] = '←'
		print-lcs(b, X, i, j − 1)

1
2
3
4
5
6
7
8
9
10

只有当碰到↖时，说明当前字符一样，作为公共子序列的一部分输出

时间复杂度，因为在构造dp[][]数组时用了外层m内层n的双重嵌套，所以复杂度为：O(mn)

最长递增子序列

Longest Increasing Subsequence，LIS

lis-length(A)
	for i = 0 to len(A)
		L[i] = 1 // 初始化每位最长长度为 1
		for j = 0 to i // 遍历A[i]之前的元素，找到当前元素的最长递增子序列，并记录长度于L[i]
			if A[j] > A[i] and L[i] + 1 > L[j]
				L[j] ← 1 + L[i]
	return max(L) // 返回L数组中的最大值

1
2
3
4
5
6
7

0/1 背包问题

Knapsack 问题

就是往背包里放东西使价值最大，限制条件是容量

线性规划问题

递归关系（状态转移方程）

j 就是当前背包空余，w 为物品重量，若 j < w，物品装不进去，为空，向后继续判断，实际上就是一个根据 w 和 j 填表格的事

i 是指从第几个物品开始往背包中放，若 j < w 即容量不够将向后递归

根据上表判断每个物品的 0/1 值（取了或者没取哪些物品）

就是看最终结果和哪一列匹配（列表示当前背包容量）

时间复杂度：O(nc)

补充背包问题：物品可以被重复取出

最优二叉搜索树

二叉搜索树：左节点小于根，右节点大于根，没有平衡限制

每个键有一个被搜索概率，要让平均搜索次数最少，这样的二叉搜索树叫做最优二叉搜索树

如

构造最优二叉搜索树递推公式

示例

查找键值：A,B,C,D
查找概率：0.1, 0.2, 0.4, 0.3

得到 c 表和 r 表

c[i,j]表示从键值i-j构造的最优二叉搜索树的平均搜索次数
r[i,j]表示从键值i-j构造的最优二叉搜索树的根，并且其左子树为r[i,k-1]，右子树为r[k+1, j]

根据 r 表构造最优二叉搜索树

伪代码

OptimalBST(p[1..n])
	for i ← 1 to n
		c[i, i − 1] ← 0
		c[i, i] ← p[i]
		r[i, i] ← i
		c[n + 1, n] ← 0
	for l ← 1 to n
		for i ← 1 to n − l + 1
			j ← i + l − 1
			minval ← ∞
			for k ← i to j
				if c[i, k − 1] + c[k + 1, j] < minval
					minval ← c[i, k − 1] + c[k + 1, j]
  					kmin ← k
				r[i, j] ← kmin
  				psum ← p[i]
				for s ← i + 1 to j
					psum ← psum + p[s]
				c[i, j] ← minval + psum
	return c[1, n], r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(n^3)

贪心算法

经典算法：活动选择问题，装载问题，哈夫曼编码，单源最短路径，最小生成树

概述：一步一步构建问题的最优解决方案，其中每一步只考虑眼前的最佳选择，不是为了找到全部解，而只是找出一种可行解（众所周知局部最优解叠加不一定是全局最优解）

贪心算法产生最优解的条件

贪心选择性：若一个优化问题的全局最优解可以通过局部最优选择得到，则该问题称为具有贪心选择性
最优子结构：若一个优化问题的最优解包括它的子问题的最优解，则称其具有最优子结构
局部最优选择

动态规划和贪心算法的明显区别：动态规划每一步做出一个选择，该选择依赖于子问题的解；贪心算法每一步做出一个选择，该选择不依赖于子问题的解

活动安排问题

就是无重叠区间，找出一系列活动中，活动区间不重叠的活动，返回不重叠的活动数量

力扣 435：无重叠区间 (opens new window)

将活动按照结束时间从小到大排序，以满足贪心选择性，遍历一次得到结果

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()){
            return 0;
        }
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v){
            return u[1]<v[1];
        });
        int ans = 1;
        int right = intervals[0][1];
        for(int i = 1; i < n; i++){
            if(intervals[i][0] >= right){
                ans++;
                right = intervals[i][1];
            }
        }
        return n-ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

因为要根据每个活动的结束时间对活动进行排序后再遍历，所以时间复杂度为

T(n) = Θ(n) + Θ(nlogn) = Θ(nlogn)

最优装载

n 为集装箱总数，c 为船载重，w 数组记录每个集装箱的重量，要求往穿上装载最多的集装箱

示例：假设 n = 3，c = 50，且 w = [10, 40, 40]

则可以将集装箱 1 和 2 装到轮船上
如果 w = [60, 70, 70]，则无法装船，即该装载问题无解

就是把重量从小到大排序，使问题满足贪心选择性，然后遍历，若可以装，则加一，否则退出

int opt_loading(int c, int[] w, int n){
    sort(w.begin(), w.end());
    int count = 0;
    for(int i: w){
        if(i <= c){
            count++;
            c -= i;
        }
    }
    return count;
}