一个人的巴黎

用户名：uq_36478041918

访问量：14986

签　名：

等　　级
排　　名	105
经　　验	8303
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

编写题解 1132: 最大数问题数组通俗易懂
浏览：755

优秀的拆分,方法都会，注意细节即可，考察递归思想
浏览：360

奖学金，运用sort函数对结构体类型排序
浏览：283

你可能喜欢

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

字符串的修改(双序列动态规划【思路详解】)

　　作者: 一个人的巴黎　　　　发表时间：2022-02-22 08:55:02 浏览：296　|　评论：1　

原题链接：字符串的修改

**解题思路：**
考虑最后一步，将A最后一个字符转化为B的最后一个字符：
1.删除A最后一个字符  ——>  考虑将A[0...n-2]变成B[0...m-1]
2.在A最后插入B[m-1]  ——>  考虑将A[0...n-1]变成B[0...m-2]
3.将A最后一个字符替换成B[m-1]  ——>  考虑将A[0...n-2]变成B[0...m-2]
4.A最后一个字符和B最后一个字符相等  ——>  考虑将A[0...n-2]变成B[0...m-2]
转移方程:        
dp[i][j]=min{dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1,dp[i-1][j-1]|A[i-1]==B[j-1]}
分别对应 情况1，2，3，4
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[200][200];//A的前i个字符A[0...i-1]和B的前j个字符B[0...j-1]的最小操作次数
string A,B;
int main()
{
    cin>>A>>B;
    int n=A.length();
    int m=B.length();
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            //空串A和串B，加加加加加...
            if(i==0){
                dp[i][j]=j;
                continue;
            }
            //串A和空串B，减减减减减...
            if(j==0){
                dp[i][j]=i;
                continue;
            }
                        // 删除       //增加
            dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
                                    //替换
            dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
            if(A[i-1]==B[j-1])//相等
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

冯海进

这代码比那些优质题解好多了，优质题解没考虑到abcd转换成bcda的情况，理论上是2，而它们是1.

2023-03-18 09:41:49

一个人的巴黎

TA的其他文章

你可能喜欢

校门外的树（C++代码）

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

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

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

【回文数(二)】（C++代码）

字符串的修改(双序列动态规划【思路详解】)

评论区

精彩推荐

【密码】（C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

Tom数（C语言代码）

分糖果（C语言代码）

时间转换（C语言代码）

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

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

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

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

Tom数（Java代码）

一个人的巴黎

TA的其他文章

你可能喜欢

校门外的树 （C++代码）

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

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

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

【回文数(二)】 （C++代码）

字符串的修改(双序列动态规划 【思路详解】)

评论区

精彩推荐

【密码】 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

Tom数 （C语言代码）

分糖果 （C语言代码）

时间转换 （C语言代码）

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

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

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

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

Tom数 （Java代码）

校门外的树（C++代码）

【回文数(二)】（C++代码）

字符串的修改(双序列动态规划【思路详解】)

　　评论区

【密码】（C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

Tom数（C语言代码）

分糖果（C语言代码）

时间转换（C语言代码）

Tom数（Java代码）