1 solutions
-
0
dp,dp[i][j]表示s的前i个字符要修改成t的前j个字符的修改数。 代码如下
#include <bits/stdc++.h> using namespace std; int dp[1005][1005]; #define INF 0x3f3f3f3f int main(){ string s,t; cin>>s>>t; memset(dp,INF,sizeof(dp)); for(int i=1;i<=s.size();i++){ for(int j=1;j<=i;j++){ if(s[i-1]==t[j-1]){//如果相同 if(dp[i-1][j-1]==INF)dp[i][j]=min(dp[i][j],0); else dp[i][j]=min(dp[i][j],dp[i-1][j-1]); } else{ if(dp[i-1][j-1]==INF) dp[i][j]=min(1,dp[i-1][j]); else{ dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]); } } } } cout<<dp[s.size()][t.size()]; return 0; }
- 1
Information
- ID
- 62
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- # Submissions
- 3
- Accepted
- 3
- Uploaded By