二维序列DP
2026-08-26 17:09:33
发布于：上海
32阅读
0回复
0点赞
二维序列DP：题目给定了两个及以上的问题数组，需要建立多维的DP数组来解决问题
1.状态解释：dp[i][j] 表示 A 数组的前 i 个元素和 B 数组的前 j 个元素中，满足题目条件的值
2.答案：一般是 dp[n][m]
3.状态转移方程：一般是通过讨论 A[i] == B[j] 或 A[i] != B[j] 的情况，来推导出 (i, j) 状态的值
4.初始化：一般是第 0 行，第 0 列
例题：
A7955.编辑距离
分析：
代码实现：
#include <bits/stdc++.h>
using namespace std;
string a, b;
int dp[2010][2010];
int main(){
cin >> a >> b;
if(a==b){
cout << 0;
return 0;
}
for(int i = 0; i <= a.size(); i++){
dp[i][0] = i;
}
for(int i = 0; i <= b.size(); i++){
dp[0][i] = i;
}
for(int i = 0; i < a.size(); i++){
for(int j = 0; j < b.size(); j++){
if(a[i]==b[j]) dp[i+1][j+1] = dp[i][j];
else dp[i+1][j+1] = min({dp[i][j], dp[i+1][j], dp[i][j+1]}) + 1;
}
}
cout << dp[a.size()][b.size()];
return 0;
}
全部评论 6
顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶2026-08-31 来自 上海
1
有帮助，赞一个