动态规划

dp[i][j]表示 s的子串a包含t的子串b的最小修改数, 其中a左端点为0,长度为j,b左端点为0,长度为i

分情况讨论:

1.当a和b的右端点相同时:

  ①若a和b长度相同 dp[i][j] = dp[i-1][j-1]
  ②若a长度大于b  dp[i][j] = min(dp[i-1][j-1], dp[i][j-1]) 分别对应a右端点在子序列和不在子序列里

2.当a和b的右端点不同时:

  ①若a和b长度相同  dp[i][j] = dp[i-1][j-1]+1
  ②若a长度大于b dp[i][j] = min(dp[i-1][j-1]+1, dp[i][j-1]) 分别对应a右端点在子序列和不在子序列里

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
string s,t;
int dp[1010][1010];


int main(){
    cin>>s>>t;
    for(int i=1; i<=t.size(); i++){
        for(int j=i; j<=s.size(); j++){
            if(t[i-1]==s[j-1]) {
                if(j == i) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j-1], dp[i][j-1]);
            }
            else {
                if(j == i) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = min(dp[i-1][j-1]+1, dp[i][j-1]);
            }
        }
    }
    cout<<dp[t.size()][s.size()];
    return 0;
}