1205: 字符串的修改 C++ 动态规划

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;

string s1;
string s2;
int L1,L2;

int dp[202][202];

int DP_(){
    //fill(dp[0],dp[0]+202*202,1);


for(int i=1;i<=L1;i++){
    for(int j=1;j<=L2;j++){
        if(s1[i-1]==s2[j-1]){
            dp[i][j]=dp[i-1][j-1];
            continue;
        }
        dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
    }
}
    /*for(int i=0;i<=L1;i++){
        for(int j=0;j<=L2;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    return dp[L1][L2];
}

main(){
    cin>>s1>>s2;
    L1=s1.length();
    L2=s2.length();
    int ans=DP_();
    cout<<ans;
}