DP关于状态转换的思路:
- 当前状态建立在之前已经求过的值(子结构)的基础上
- 状态转换考虑最后一步(例外,LIS模型)
- 初始状态 f[0][j] = f[i][0] = 0
1.编辑距离
分析:
1. 状态表示 f[i][j]
集合 A的0~i变为B的0~j所有方案
属性 min操作次数最小值
2. 状态转换 删除/插入/替换
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1)
(按照定义:f[i-1][j]是A的0~i-1变为B的0~j所有方案)
f[i][j] = min(f[i][j], a[i] == b[j] ? f[i - 1][j - 1] : f[i - 1][j - 1] + 1)
(按照定义:f[i-1][j-1]是A的0~i-1变为B的0~j-1所有方案)
code1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n;
//1 f[i][0]只能通过删除i次实现 同理下一步只能增加
for(int i = 1; i <= n; ++i) cin >> a[i], f[i][0] = i;
cin >> m;
for(int j = 1; j <= m; ++j) cin >> b[j], f[0][j] = j;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
//2 删除/增加
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
//3 如果两个串最后一位相等,不需要替换;否则替换
f[i][j] = min(f[i][j], a[i] == b[j] ? f[i - 1][j - 1] : f[i - 1][j - 1] + 1);
}
}
cout << f[n][m] << endl;
}
code2
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1005;
int n, m;
//1 DP中写成C风格字符串比较好,因为常用从1开始赋值
char str[N][15];
int f[N][N];
//2 两个字符串之间的关系的时候,类型要统一,不要一个是string类型,一个是char[]
int query(char s[], char t[])
{
//3
//1 C风格 字符数组长度取法 距离取多少
int len1 = strlen(s + 1), len2 = strlen(t + 1);
//2 比较字符数组
//strcmp
//int strcmp(const char* str1, const char* str2);
// 其中 str1 和 str2 分别是要比较的两个字符串。
// 函数会按照字典序比较两个字符串,
// 如果 str1 大于 str2,则返回正整数;
// 如果 str1 小于 str2,则返回负整数;如果两个字符串相等,则返回 0。
//3 拷贝字符数组
// strcpy
// strcpy() 函数是 C++ 语言中用于字符串复制的函数,其函数原型为:
// char* strcpy(char* destination, const char* source);
// 其中 destination 是要将源字符串复制到的目标字符串,source 是要复制的源字符串。
// 函数会将源字符串中的所有字符(包括结尾的空字符 '\0')复制到目标字符串中,
// 并返回指向目标字符串的指针。
for(int i = 0; i <= len1; ++i) f[i][0] = i;
for(int j = 0; j <= len2; ++j) f[0][j] = j;
for(int i = 1; i <= len1; ++i) {
for(int j = 1; j <= len2; ++j){
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
f[i][j] = min(f[i][j], s[i] == t[j] ? f[i - 1][j - 1] : f[i - 1][j - 1] + 1);
}
}
return f[len1][len2];
}
int main()
{
cin >> n >> m;
//4 输入到下标1的位置
for(int i = 0; i < n; ++i) cin >> str[i] + 1;
for(int i = 0; i < m; ++i){
char s[N];
int limit;
cin >> s + 1 >> limit;
int cnt = 0;
for(int i = 0; i < n; ++i){
if(query(str[i], s) <= limit) cnt ++;
}
cout << cnt << endl;
}
}
2.最长公共子序列
https://www.acwing.com/problem/content/899/
- 状态表示
f[i][j]
集合:A的0~i与B的0~j所有公共子序列
属性: max长度最大 - 状态转换 f[i][j]
f[i][j] = max
if a[i]==b[j] f[i - 1][j - 1] + 1
else max(f[i][j - 1], f[i - 1][j])
code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int j = 1; j <= m; ++j) cin >> b[j];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
else{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
}
}
cout << f[n][m] << endl;
}
3.最长上升子序列模型
https://www.acwing.com/problem/content/1014/
code1
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5010;
typedef pair<int, int> PII;
int n;
PII a[N];
int f[N];
int main()
{
cin >> n;
for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
//1 猜一下 先排个序
sort(a, a + n);
for(int i = 0; i < n; ++i){
f[i] = 1;
for(int j = 0; j < i; ++j){
if(a[i].second > a[j].second) f[i] = max(f[i], f[j] + 1);
}
}
int res = 0;
for(int i = 0; i < n; ++i) res = max(res, f[i]);
cout << res;
}
https://www.acwing.com/problem/content/1018/
状态表示:f[i]
集合:0~i以a[i]结尾的所有的上升子序列
属性:max最大和
状态转换:
f[i]初始值为1
集合划分:f[i] = a[i] > a[k] ? f[i-1],f[i-2]…f[1],f[0] + a[k] (k对应f的下标) : f[i]
对于每一个i,对于所有的j(0 <= j < i) ,若a[i]大于a[j],则可以尝试更新f[i]
遍历所有f,取最大值即为最大上升子序列和
code2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N];
int main()
{
cin >> n;
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < n; ++i){
f[i] = a[i];
for(int j = 0; j < i; ++j){
if(a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
}
}
int res = -1;
for(int i = 0; i < n; ++i){
res = max(res, f[i]);
}
cout << res << endl;
}