fork download
copy 
  1. /*
  2. dp[i][j] số thao tác ít nhất để biến dãy số từ 1 đến i t hành từ 1 đến j
  3. dp[i][j]=min(dp[i-1][j]+1(xóa), dp[i-1][j-1]+(1 nếu a[i]!=a[j]) (thay thế), dp[i][j-1]+1(thêm))
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. const long long MaxN = 5005;
  8. long long dp[MaxN][MaxN];
  9. string n,m;
  10.  
  11. void input()
  12. {
  13.     cin >> n >> m;
  14. }
  15.  
  16. void solve()
  17. {
  18.     n=" " + n;
  19.     m=" " + m;
  20.     long long len1 = n.size() - 1;
  21.     long long len2 = m.size() - 1;
  22.  
  23.     for(long long i=0;i<=len1;i++)
  24.         dp[i][0]=i;
  25.  
  26.     for(long long j=0;j<=len2;j++)
  27.         dp[0][j]=j;
  28.  
  29.     for(long long i=1;i<=len1;i++)
  30.     {
  31.         for(long long j=1;j<=len2;j++)
  32.         {
  33.             dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
  34.             dp[i][j]=min(dp[i][j],
  35.                          dp[i-1][j-1]+(n[i]!=m[j]));
  36.         }
  37.     }
  38.  
  39.     cout << dp[len1][len2];
  40. }
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(0);
  45.     cin.tie(0);
  46.  
  47.     input();
  48.     solve();
  49. }
  50.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/of0zNu
language:
C++14 (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!