二维序列DP

永安.11.23

2026-08-27 19:00:11

发布于：上海

18阅读

0回复

0点赞

二维序列DP:题目给定了两个或两个以上的问题数组，需要建立多维的DP数组，解决问题

1.状态设计：dp[ i ][ j ] 表示 A 数组的前 i 个元素和 B 数组的前 j 个元素中，满足题目条件的值
最长公共子序列：dp[ i ][ j ]表示字符串 x 前 i 个字符与字符串 y 前 j 个字符的最大公共长度

2.答案：一般是 dp[ n ][ m ]
最长公共子序列：dp[ n ][ m ]

3.转移方程：一般是通过比较 A[ i ] == B[ j ] 或 A[ i ] != B[ j ] 的情况，来推导出 ( i , j )状态的值
最长公共子序列：
如果 A[ i ] 与 B[ j ] 相等：dp[ i ][ j ] 为 dp[ i-1 ][ j-1 ]+1
否则：dp[ i ][ j ] 为 dp[ i-1 ][ j ]，dp[ i ][ j-1 ]，dp[ i-1 ][ j-1 ]的最大值

4.初始化：一般是第 0 行，第 0 列

1.最长公共子序列

    x = '0'+x;
    y = '0'+y;

    for(int i = 1;i<x.size();i++){
        for(int j = 1;j<y.size();j++){
            if(x[i]==y[j]){
                f[i][j] = f[i-1][j-1]+1; // 增加1
            }else{
                f[i][j] = max({f[i-1][j],f[i][j-1],f[i-1][j-1]}); // 延续上次的最大值
            }
        }
    }
    cout << f[x.size()-1][y.size()-1];

2.编辑距离

    a = '0'+a;
    b = '0'+b;

    for(int i = 0;i<=a.size();i++){  // 初始化为i，可能从边界延续
        f[i][0] = i;
    }for(int i = 0;i<=b.size();i++){ // 初始化为0则会影响else中取最小值，
        f[0][i] = i; // 初始化为1e9则会影响从f[i-1][j-1]的延续
    }

    for(int i = 1;i<a.size();i++){
        for(int j = 1;j<b.size();j++){
            if(a[i]==b[j]){
                f[i][j] = f[i-1][j-1]; // 直接延续
            }else{
                f[i][j] = min({f[i-1][j],f[i][j-1],f[i-1][j-1]})+1; // 取最小值+1，
            }
        }
    }
    cout << f[a.size()-1][b.size()-1];