应当明天继续

用户名：mr1269410697

访问量：1692

签　名：

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

　　自我简介：

TA的其他文章

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

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

你可能喜欢

C语言训练-最大数问题（C语言代码）.........关于-1

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

　　作者: 应当明天继续　　　　发表时间：2019-10-07 11:35:41 浏览：766　|　评论：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语言代码）

C二级辅导-计负均正（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

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

C语言训练-最大数问题（C语言代码）.........关于-1

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

评论区

精彩推荐

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

Biggest Number （C++代码）回溯法

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

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

数对（C语言代码）

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

震宇大神的杀毒软件（C语言代码）

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

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

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

应当明天继续

TA的其他文章

你可能喜欢

数据结构-有序线性表的有序合并 （C语言代码）

C二级辅导-计负均正 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

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

C语言训练-最大数问题 （C语言代码）.........关于-1

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

评论区

精彩推荐

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

Biggest Number （C++代码）回溯法

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

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

数对 （C语言代码）

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

震宇大神的杀毒软件 （C语言代码）

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

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

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

数据结构-有序线性表的有序合并（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

　　评论区

数对（C语言代码）

震宇大神的杀毒软件（C语言代码）