蓝桥杯2019年第十届国赛真题-最优包含_最长子序列2019国赛试题f

题目

题目链接

题解

动态规划。

---

（有点像最长公共子序列）

状态定义：dp[i][j]表示S前i个字符要想包含T前j个字符，需要经过的最少修改次数。

转移方程：
① S[i] == T[j]：此时无需进行变换，S前i个字符要想包含T前j个字符需要经过的最少修改次数就等于S前i-1个字符要想包含T前j-1个字符需要经过的最少修改次数，即dp[i][j] = dp[i-1][j-1]
② S[i] != T[j]：两种情况转移而来。其一，为了让S前i个字符包含T前j个字符，我们只需要让让S前i-1个字符包含T前j-1个字符，同时将S[i]修改成T[j]，即dp[i][j] = dp[i-1][j-1] + 1；其二，S前i-1个字符包含T前j个字符的修改次数更少的话，我们也可以不修改S[i]而是直接在第i个字符之前就已经包含T前j个字符了，即dp[i][j] = dp[i-1][j]

初始化：用S的前任意个字符都可以包含T的前0个字符，修改个数为0，所以dp[i][0] = 0。

---

自己写的时候写（蒙）的代码就比标准答案在不相等的情况下，多了个对dp[i][j-1]取min，其他完全一样，但还是错了，而且是蒙的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
string s, t;
int f[N][N];
int main()
{
	cin >> s >> t;
	int n = s.size(), m = t.size();
	s = '.' + s, t = '.' + t;
	
	memset (f, 0x3f, sizeof f);
	for (int i = 0;i <= n;i ++) f[i][0] = 0; // 初始化 
	
	for (int i = 1;i <= n;i ++)
	for (int j = 1;j <= m && j <= i;j ++) 
		if (s[i] == t[j]) f[i][j] = f[i-1][j-1];
		else f[i][j] = min (f[i-1][j-1] + 1, f[i-1][j]);
	
	cout << f[s.size()-1][t.size()-1];

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