一个人的巴黎

用户名：uq_36478041918

访问量：13190

签　名：

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

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

　　作者: 一个人的巴黎　　　　发表时间：2022-02-22 08:55:02 浏览：273　|　评论：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语言代码）

C语言训练-谁家孩子跑最慢* （C语言代码）

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

母牛的故事（C语言代码）

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

评论区

精彩推荐

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

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

程序员的表白（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

wu-淘淘的名单（C++代码）

母牛的故事（C语言代码）

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

1118（求助_已解决）

一个人的巴黎

TA的其他文章

你可能喜欢

整除问题 （C语言代码）

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

C语言训练-谁家孩子跑最慢* （C语言代码）

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

母牛的故事 （C语言代码）

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

评论区

精彩推荐

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

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

程序员的表白 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

wu-淘淘的名单 （C++代码）

母牛的故事 （C语言代码）

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

1118（求助_已解决）

整除问题（C语言代码）

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

母牛的故事（C语言代码）

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

　　评论区

程序员的表白（C语言代码）

wu-淘淘的名单（C++代码）

母牛的故事（C语言代码）