应当明天继续

用户名：mr1269410697

访问量：1548

签　名：

等　　级
排　　名	4842
经　　验	1565
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	SEU
专　　业

　　自我简介：

TA的其他文章

字符串的修改-题解(C++代码)---动态规划
浏览：722

字符串的查找删除-题解(C++代码)
浏览：427

你可能喜欢

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

字符串的修改-题解(C++代码)---动态规划

　　作者: 应当明天继续　　　　发表时间：2019-10-07 11:35:41 浏览：722　|　评论：5　

原题链接：字符串的修改

// 感觉测试用例不全，用长度减去相同字符个数，没有考虑既要插入又要删除的情况
// 举个例子：
// s1串：abcde
// s2串：gabce
// 串长度减去相同字符个数5-4=1，但显然是要在s1串插入g删除b，2次操作
// 正确的做法应该是用动态规划
// dp[i][j]表示s1[0]-s1[i]子串变成s2[0]-s2[j]一样所需要的字符操作次数
// 若s1[i]==s2[j]，则dp[i][j]==dp[i-1][j-1]，表示不需要操作
// 若s1[i]!=s2[j]，则可能的操作有替换、插入、删除三种方法，分别由前一步得出，并取最小值。
// dp[i-1][j]+1表示往s1插入，dp[i][j-1]+1表示往s2插入，dp[i-1][j-1]+1表示替换当前字符。

```cpp
#include <iostream>
#include <string>
using namespace std;

int myMin(int a, int b) {
    return a < b ? a : b;
}

int main()
{
    string s1, s2;
    int dp[100][100];
    cin >> s1 >> s2;
    for (int i = 0; i < s2.length(); ++i) dp[0][i] = i;
    for (int i = 0; i < s1.length(); ++i) dp[i][0] = i;
    for (int i = 1; i <= s1.length(); ++i) {
        for (int j = 1; j <= s2.length(); ++j) {
            if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else {
                dp[i][j] = myMin(myMin(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1), dp[i][j - 1] + 1);
            }
        }
    }
    cout << dp[s1.length()][s2.length()] << endl;
    return 0;
}
```

0.0分

21 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

不惧黑夜

太强了太强了

2022-08-26 19:29:59

这才对嘛

2022-01-05 16:56:03

A白旭002

这个思路和流程才对，前面的那些逻辑上有问题

2020-12-10 16:33:35

看了好几个，终于看到正解了，前面几个能过完全是因为数据太水了

2020-03-24 20:49:07

陈正磊

正解

2020-02-20 19:47:12

应当明天继续

TA的其他文章

你可能喜欢

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

字符串的修改-题解(C++代码)---动态规划

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

【密码】（C语言代码）

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1024题解

应当明天继续

TA的其他文章

你可能喜欢

数字整除 （C++代码）——(22行代码)真的只需要两个变量就够了

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

字符串的修改-题解(C++代码)---动态规划

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

【密码】 （C语言代码）

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1024题解

数字整除（C++代码）——(22行代码)真的只需要两个变量就够了

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

　　评论区

【密码】（C语言代码）

字符串的输入输出处理（C语言代码）