题目链接

洛谷P2758

题目分析

(一个大佬的思路,我是搬运工)
1.确定子问题:
由于对于字符串的操作只有4种情况(删除,添加、更改、不变),所以该题的子问题就是进行了这4种操作后的A字符串变为B字符串需要多少步。

2.定义状态:
也就是说递归的dp函数需要哪些参数,参数越少越好因为需要建memo。后来想到dp(i,j)代表字符串A的前i个字符(包括第i个)变为字符串B的前j个(包括第j个)需要多少步。也就是说解出来dp(lenA,lenB)就可以了。

3.转移方程:
删:dp(i-1,j)+1 //字符串A的前i-1个字符变为字符串B的前j个需要多少步 【把字符串的第i个字符(最后一个)删除了】,删除需要一步因此加1

添:dp(i,j-1)+1 //将B[j]字符加在A字符串的最后面即添加,同样可以理解为将B[j]字符删掉(因为不用再考虑了)。
//字符串A的前i个字符变为字符串B的前j-1个需要多少步 添加需要一步因此加1

替:dp(i-1,j-1)+1 //字符串A和B的最后两个都相等了,因此都不用再考虑
//字符串A的前i-1个字符变为字符串B的前j-1个需要多少步 添加需要一步因此加1

不变:dp(i-1,j-1)//字符串A和B的最后两个都相等,不考虑。感性的说这种情况是理想情况。

4.避免重复求解
这个最简单,建个数组就行。

题目代码

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-x))
using namespace std;

typedef long long ll;
const int N = 2010;

int dp[N][N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.size(), len2 = s2.size();
    for (int i = 1; i <= len1; i++) dp[i][0] = i;
    for (int i = 1; i <= len2; i++) dp[0][i] = i;
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }
    cout << dp[len1][len2];

    return 0;
}
最后修改:2020 年 12 月 06 日 10 : 43 PM