Table of contents

• Problem
• Time complexity
• Solution

# Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_E&lang=ja#

# Time complexity

$O(N^2)$

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_S 1001

string S1, S2;
Int dp[MAX_S][MAX_S];

void input() {
  cin >> S1 >> S2;
}

void solve() {
  loop(c1,0,S1.length()+1) {
    loop(c2,0,S2.length()+1) {
      if (c1 == 0) dp[c1][c2] = c2;
      else if (c2 == 0) dp[c1][c2] = c1;
      else if (S1[c1-1] == S2[c2-1]) {
        dp[c1][c2] = dp[c1-1][c2-1];
      } else {
        dp[c1][c2] = 1 + min(min(dp[c1-1][c2], dp[c1][c2-1]), dp[c1-1][c2-1]);
      }
    }
  }
  
  cout << dp[S1.length()][S2.length()] << endl;
}

int main() {
  input();
  solve();
}