二维序列DP

EasonH

2026-08-26 17:09:33

发布于：上海

24阅读

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;
}