《算法设计与分析》第三章：动态规划

前言

本篇博客内容为《算法设计与分析》（耿国华版）第三章：动态规划的作业和算法积累，更多动态规划内容可以参考本人其他相关博客如下：

动态规划-背包问题详解
动态规划-线性Dp和区间Dp详解
动态规划-线性Dp进阶详解
动态规划-计数、数位统计、状态压缩、树形、记忆化搜索Dp

一、本章作业

1.子序列问题

子序列是字符串的若干字符（可能不连续，但前后关系不能变）构成的序列；子串是字符串的若干连续字符构成的序列。给定两个字符序列A和B：

（1）求两个序列的最长公共子序列的长度，并输出该子序列（输出一种即可）。

【DP数组含义】

• f[i][j]表示所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现的子序列集合中，取最长公共子序列的长度值，即为f[i][j]的值

【状态转移方程】

• f[i][j] = max(f[i][j],f[i-1][j], f[i][j-1])
• 两个序列分别是a[i]、b[j]，我们则可以把f[i][j]分为四种情况，不包含a[i]不包含b[j]、不包含a[i]包含b[j]、包含a[i]不包含b[j]、包含a[i]包含b[j]
• 不包含a[i]包含b[j]：f[i-1][j]包含该种情况，该情况是f[i-1][j]的子集，因为f[i-1][j]可能包含b[j]也可能不包含b[j]（包含a[i]不包含b[j]同理）
• 包含a[i]包含b[j]：这种情况必须满足a[i] == b[j]，f[i-1][j-1]+1
• 不包含a[i]不包含b[j]：已经包含在f[i-1][j]里了

【算法实现与运行截图】

#include<bits/stdc++.h>

using namespace std;

const int Size = 1010;  
int c[Size][Size]; //dp数组
int b[Size][Size];    

int LCS_length(string X, string Y)
{
    int m = X.size();
    int n = Y.size();
    for(int i=1; i<=m; i++)
	{
		c[i][0] = 0;
	} 
	for(int j=1; j<=n; j++)
	{
		c[0][j] = 0;
	} 
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(X[i-1] == Y[j-1]) 
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            }
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
    }
    return c[m][n]; //最长公共子序列的长度 
}
void LCS(string X, int i, int j)
{
    if(i==0 || j==0) return;
    if(b[i][j] == 1) 
    {
        LCS(X, i-1, j-1);
        cout<<X[i-1];  //a[i-1]==b[j-1]
    }
    else if(b[i][j]==2) LCS(X, i-1, j);
    else if(b[i][j]==3) LCS(X, i, j-1);
}
int main()
{
    string X, Y;
    cin>>X>>Y;
    cout<<"最大公共子序列长度为:"<<LCS_length(X, Y)<<endl;
    cout<<"最大公共子序列为:";
    LCS(X, X.size(), Y.size());
    
    return 0;
}

（2）求两个序列的最长公共子串的长度，并输出该子串（输出一种即可）。

【DP数组含义】

• f[i][j]表示所有在第一个序列且以a[i]结尾的子串，且在第二个序列且以b[i]结尾的子串，取最长公共子序列的长度值，即为f[i][j]的值

【状态转移方程】

• f[i][j] = max(f[i][j],f[i-1][j-1] + 1)

【算法实现与运行截图】

#include<bits/stdc++.h>

using namespace std;

int main()
{
	string s1,s2;
	cin>>s1>>s2;
	if(s1.size() > s2.size()) //以短的作为s1
		swap(s1,s2);
	int len1 = s1.size(), len2 = s2.size();
	int start = 0, mx = 0; //记录结果
	vector<vector<int> > dp(len1+1,vector<int>(len2+1,0));
	for(int i = 1;i<=len1;i++)
	{
		for(int j = 1;j<=len2;j++)
		{
			if(s1[i-1] == s2[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			if(dp[i][j] > mx)
			{
				mx = dp[i][j];
				start = i - mx;
			}
		}
	}
	cout<<"最长公共子串长度："<<mx<<endl;
	cout<<"最长公共子串为："<<s1.substr(start,mx)<<endl;
	return 0;
}

2.0-1背包问题

用动态规划求解0-1背包问题。输出放置哪几件物品使得背包价值最大？背包价值是多少？

【DP数组含义】

• f[i][j]表示在前i种物品种选取，使得容量不超过j，满足该情况的所有情况集合，在集合中选取最优解，该最优解的质量即为f[i][j]的值

【状态转移方程】

• f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i-1][j])
• 优化为二维：f[j]=max(f[j],f[j-v[i]]+w[i])

【算法实现与运行截图】

#include <bits/stdc++.h>

using namespace std;

const int N=105;
int w[N]; //重量
int v[N]; //价值
int path[N][1005];//path[i][j] 
int dp[1005];  //dp[i][j]的优化

int main()
{ 
	int n,m;//商品件数和背包容量 ,要取得最大的价值 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			path[i][j]=0;	
			if(dp[j-w[i]]+v[i]>dp[j])
			{
				path[i][j]=1;
				dp[j]=dp[j-w[i]]+v[i];
			}
		} 
	} 
	cout<<"最大背包价值："<<dp[m]<<endl;
	stack<int> st;
	int i=n;
	int j=m;
	while(i>0&&j>0)
	{
		if(path[i][j]==1)
		{	
			st.push(i);
			j-=w[i];
		}
		i--;
	}
	cout<<"所选物品：";
	while(!st.empty())
	{
		cout<<st.top()<<' ';
		st.pop();
	}
	return 0;
}

3.设备分配问题

某企业根据计划安排，拟将n台相同的设备分配给m个子公司，各子公司获得这种设备后，可以盈利Cij(i台设备提供给j号子公司将得到的利润，1≤i≤n，1≤j≤m) 。问如何分配设备，才使这批设备利益最大化？

【DP数组含义】

• dp[i][j] 表示前 i 台设备分配给前 j 个子公司所能获得的最大利润

【状态转移方程】

• dp[i][j] = max(dp[i][j], dp[i - k][j - 1] + profit[k][j])

【算法实现与运行截图】

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 105;

int dp[MAXN][MAXN]; // dp[i][j] 表示前 i 台设备分配给前 j 个子公司所能获得的最大利润
int profit[MAXN][MAXN]; // 存储利润表，profit[i][j] 表示将 i 台设备分配给第 j 个子公司可以获得的利润

// 设备分配函数
int allocateDevices(int n, int m, vector<vector<int>>& c) 
{	
	// 根据提供的利润表，填充 profit 数组
	for (int i = 1; i <= n; ++i) 
	{
		for (int j = 1; j <= m; ++j) 
		{
			profit[i][j] = c[i][j];
		}
	}
	
	// 动态规划求解最大利润
	for (int i = 1; i <= n; ++i) 
	{
		for (int j = 1; j <= m; ++j) 
		{
			for (int k = 0; k <= i; ++k) 
			{
				dp[i][j] = max(dp[i][j], dp[i - k][j - 1] + profit[k][j]);
			}
		}
	}
	
	return dp[n][m]; // 返回最大利润
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n, m;
	cout << "请输入设备数量n和子公司数量m：" << endl;
	cin >> n >> m;
	
	vector<vector<int>> c(n + 1, vector<int>(m + 1, 0));
	cout << "请依次输入各个设备在各个子公司的利润：" << endl;
	for (int i = 1; i <= n; ++i) 
	{
		for (int j = 1; j <= m; ++j) 
		{
			cin >> c[i][j];
		}
	}
	
	int maxProfit = allocateDevices(n, m, c);
	cout << "最大利润为：" << maxProfit << endl;
	
	return 0;
}

4. 合唱队形问题

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，而不改变其他同学的位置，使得剩下的K位同学排成合唱队形。合唱队形要求：设K位同学从左到右依次编号为1，2，…，K，他们的身高分别为T1,T2，…，TK，则他们的身高满足：
T1<…<Ti, 且Ti>Ti+1>…>TK(1<=i<=K)。
当给定队员人数N和每个学生的身高T[i]时，需要多少学生出列，可以得到最长的合唱队形。你也可以尝试输出需要出列哪些学生。

【算法思想】

• 用两个dp数组：l[i]代表从左开始以a[i]结尾的最长子序列长度为多少，r[i]代表从右开始以a[i]结尾的最长子序列长度为多少
• 从左到右遍历l：a[i]>a[j]&&sum<l[j]时，l[i] = l[j] + 1
• 从右到左遍历m：a[i]>a[j]&&sum<m[j]时，m[i] = m[j] + 1
• 最后将两者遍历相加取最大值即可

【算法实现与运行截图】

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int main()
{
	int n = 0;
	cin>>n;
	int a[N] = {0};
	int l[N] = {0};
	int m[N] = {0};
	for(int i = 0;i<n;i++)
	{
		cin>>a[i];
		l[i] = 1;
		m[i] = 1;
	}
		
	for(int i = 0;i<n;i++) 
	{
		int sum = INT_MIN;
		for(int j = 0;j<i;j++)
		{
			if(a[i]>a[j]&&sum<l[j])
			{
				sum = l[j];
				l[i] = l[j] + 1;
			}
		}
			
	}
		
	for(int i = n-1;i>=0;i--)
	{
		int sum = INT_MIN;
		for(int j = n-1;j>i;j--)
		{
			if(a[i] > a[j] && sum < m[j])
			{
				sum = m[j];
				m[i] = m[j] + 1;
			}
		}
	}
		
	int s = INT_MIN;
	for(int i = 0;i<n;i++)	
	{
		if(s<(l[i] + m[i] - 1) )
		{
			s = l[i] + m[i] - 1;
		}
	}
	cout<<n-s<<endl;
	return 0;
}

【时空复杂度】

• 时间复杂度： O(n^2)
• 空间复杂度： O(N)

5. 石子合并问题

路边n堆石子排成一排，每堆石子个数不一。现要将石子有序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的耗费力气。试设计一个算法，计算将 n 堆石子合并成一堆的最省力气数。
例如有 4 堆石子分别为 1，3，5，2， 如果先合并 1、2 堆，代价为 4，得到 4，5，2；又合并 1，2 堆，代价为 9，得到 9，2 ；再合并得到 11，总代价为 4+9+11=24。如果第二步是先合并 2，3 堆，则代价为 7，得到 4，7，最后一次合并代价为 11，总代价为 4+7+11=22。

【算法思想】

• 状态表示：f[i][j]表示将第i堆石子和第j堆石子合并的所有方法的集合中，取代价最小值的最优解，f[i][j]的值即为该最小值
• 状态计算：可以从第i堆石子和第j堆石子合并方法的最后一次合并在何处后入手
• 利用前缀和：定义为数组s[N]
• 综上：f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1])

【算法实现与运行截图】

#include<bits/stdc++.h>

using namespace std;

const int N = 110,INF = 1e9;

int n;
int s[N];
int f[N][N];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
	
	for(int i = 1; i <= n; i ++ ) s[i] += s[i-1]; //计算前缀和
	
	for(int len = 2; len <= n; len ++ ) //遍历每种长度 
		for(int i = 1; i + len - 1 <= n; i ++ ) //遍历每种起点 
		{
			int l = i, r = i + len - 1;
			f[l][r] = INF;//初始化，全局变量初始值为0 
			
			for(int k = l; k < r; k ++ )
				f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l-1]);
		}
		
	printf("%d\n",f[1][n]);
	
	return 0;
}

【时空复杂度】

• 时间复杂度： O(n^3)
• 空间复杂度： O(N^2)

二、算法积累

1. 奇葩国家钞票问题

如果某奇葩国家的钞票面额分别是1、5、11，如何凑n元的面额，用张数尽量少的钞票？

• 状态表示：dp[i]凑i元的面额最少需要多少张钞票
• 状态计算：dp[i] = min(dp[i-1], dp[i-5],dp[i-11])

#include <bits/stdc++.h>

using namespace std;

const int MMM = 105;
const int INF = 0x3f3f3f3f;

int n;
int c1, c2, c3;
int dp[MMM];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	
	for(int i = 1; i <= n; i ++ )
	{
		c1 = INF, c2 = INF, c3 = INF;
		if(i - 1 >= 0) c1 = dp[i - 1] + 1;
		if(i - 5 >= 0) c2 = dp[i - 5] + 1;
		if(i - 11 >= 0) c3 = dp[i - 11] + 1;
		dp[i] = min(min(c1, c2),c3);
	}
	
	cout << "所需纸币张数：" << dp[n] << endl;
	
	return 0;
}

2. 组合数问题

求C_n^m，输入n和m，输出结果

• 状态表示：dp[i][j]表示C_i^j的结果
• 状态计算：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]（排除i == j时等于1）

#include <bits/stdc++.h>

using namespace std;

const int MMM = 105;

int dp[MMM][MMM];

int ComB(int n, int m)
{
	for(int i = 1; i <= n; i ++ ) dp[i][0] = 1;
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
			if(i == j) dp[i][j] = 1;
			else if(i > j) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
	
	return dp[n][m];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	cout << ComB(n, m) << endl;
	
	return 0;
}

3. n的k分解问题

求将正整数n无序拆分成最大数为k（称为n的k拆分）的拆分方案个数，要求所有的拆分方案不重复

• 状态表示：f[i][j]表示i的j拆分方案数
• 状态计算：
  

#include <bits/stdc++.h>

using namespace std;

const int MMM = 105;

int dp[MMM][MMM];

int Split(int n, int k)
{
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= k; j ++ )
		{
			if(i == 1 || j == 1) dp[i][j] = 1;
			else if(i < j) dp[i][j] = dp[i][i];
			else if(i == j) dp[i][j] = dp[i][j - 1] + 1;
			else if(i > j) dp[i][j] = dp[i][j - 1] + dp[i - j][j];
		}
	
	return dp[n][k];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	cout << Split(n, k) << endl;
	
	return 0;
}

4. 矩阵连乘问题

给定n个矩阵｛A1,A2,…,An｝，其中，Ai与Ai+1是可乘的(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的次数最小。

• 状态表示：dp[i][j]表示矩阵连乘的最优值（所需乘法的最少次数）
• 状态计算：（设矩阵Ai的行分别为pi）
  

#include<bits/stdc++.h>

using namespace std;

const int MMM = 100;

int p[MMM];
int m[MMM][MMM],s[MMM][MMM];
int n;

void matrixchain()
{
	for(int r=2;r<=n;r++)//矩阵连乘的规模为r
	{
		for(int i=1;i<=n-r+1;i++)
		{
			int j=i+r-1;
			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//对m[][]开始赋值
			s[i][j]=i;//s[][]存储各子问题的决策点
			for(int k=i+1;k<j;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;
				}
			}
		}
	}
}

void print(int i,int j)
{
	if(i == j)
	{
		cout<<"A["<<i<<"]";
		return;
	}
	cout<<"(";
	print(i,s[i][j]);
	print(s[i][j]+1,j);//递归1到s[1][j]
	cout<<")";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cout<<"请输入矩阵的个数n : "<<endl;
	cin>>n;
	cout<<"请依次输入每个矩阵的行数和最后一个矩阵的列数："<<endl;
	for(int i=0;i<=n;i++) cin>>p[i];
	
	matrixchain(); 
	print(1,n);
	cout<<endl;
	
	cout<<"最小计算量的值为："<<m[1][n]<<endl;
	
	return 0;
}

5. 整数分解问题

求将正整数n无序拆分的拆分方案个数，要求所有的拆分方案不重复

• 状态表示：f[i][j]表示i的j拆分方案数
• 状态计算：
  

#include <bits/stdc++.h>

using namespace std;

const int MMM = 105;

int dp[MMM][MMM];

int Split(int n, int k)
{
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= k; j ++ )
		{
			if(i == 1 || j == 1) dp[i][j] = 1;
			else if(i < j) dp[i][j] = dp[i][i];
			else if(i == j) dp[i][j] = dp[i][j - 1] + 1;
			else if(i > j) dp[i][j] = dp[i][j - 1] + dp[i - j][j];
		}
	
	return dp[n][k];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n ;
	cout << Split(n, n) << endl;
	
	return 0;
}

6. 字符串编辑距离问题

设A和B是两个字符串，现在要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作包括3种：
（1）删除一个字符。
（2）插入一个字符。
（3）将一个字符替换另一个字符。
求将字符串A转换为字符串B的最少操作次数。
例如，A=“sfdqxbw”，B=“gfdgw”，结果为4。

• 状态表示：两个数组分别表示为a[N]、b[N]，则f[i][j]表示所有将a[1…i]变成b[1…j]的操作方式集合中，操作次数最少的方案，该方案的操作次数即为f[i][j]的值
• 状态计算：我们可以将f[i][j]的计算从其上一步来源出发，即a的最后一个元素a[i]要如何处理，分为三种情况：增、删、改（有条件）
  • 增：f[i][j-1]+1
  • 删：f[i-1][j]+1
  • 改：a[i]==b[j]则f[i-1][j-1]，a[i]!=b[j]则f[i-1][j-1]+1

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
	scanf("%d%s", &n, a + 1);
	scanf("%d%s", &m, b + 1);
	
	//初始化 
	for(int i = 0; i <= m; i ++ ) f[0][i] = i; //全增 
	for(int i = 0; i <= n; i ++ ) f[i][0] = i; //全删 
	
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
		{
			f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
			if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
			else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
		}
		
	printf("%d\n", f[n][m]);
	
	return 0;
}

7.括号匹配问题

给一个字符串，里面只包含’(‘,’[‘,’{‘,’}‘,’]‘,’)'六种符号，请问需要至少添加多少个括号才能使这些括号匹配

• 状态表示：
• 状态计算：