yukicoder No.225 文字列変更(medium)

yukicoderに参戦。No.225は解けなかったけれど、自分にとって良いレベルの問題だったためメモ。
コンテスト中に書いたコードは以下の通り。

#include <iostream>
#include <algorithm>
using namespace std;

int solve(string s, string t, int n, int m, int itr = 0){
  if(itr == m)
    return 0;
  if(itr == n)
    return m - n;
  if(s[itr] == t[itr])
    return solve(s, t, n, m, itr + 1);

  int mincost;
  mincost = solve(s, t, n, m, itr + 1) + 1;
  mincost = min(mincost, solve(s.substr(1, n - 1), t, n - 1, m, itr) + 1);
  mincost = min(mincost, solve("a" + s, t, n + 1, m, itr + 1) + 1);
  return mincost;
}

int main(){
  int n, m;
  cin >> n >> m;
  string s, t;
  cin >> s >> t;
  cout << solve(s, t, n, m) << endl;
}

基本的に考え方はこれで良かったはず。TLEになってしまいましたが、自分の中ではここまでコードを書けるようになってすこし満足。でも、上を見ましょう。後はこれをDynamic Programmingで効率的に解きましょう。

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 1100
#define INF 1<<29

void chmin(int& a, int b){
  if(a > b)
    a = b;
}

int n, m;
string S, T;
int dp[MAX][MAX];

int main(){
  cin >> n >> m;
  cin >> S >> T;
  S += "-"; T += "-";
  for(int i = 0; i < MAX; i++)
    for(int j = 0; j < MAX; j++)
      dp[i][j] = INF;
  dp[0][0] = 0;
  for(int i = 0; i <= n; ++i){
    for(int j = 0; j <= m; ++j){
      if(S[i] == T[j])
        chmin(dp[i+1][j+1], dp[i][j]);
      else
        chmin(dp[i+1][j+1], dp[i][j] + 1);
      chmin(dp[i+1][j], dp[i][j] + 1);
      chmin(dp[i][j+1], dp[i][j] + 1);
    }
  }
  cout << dp[n][m] << endl;
}

模範解答をほぼ丸パクリですね...でも良い勉強になりました。
全探索が出来るようになってきたのでDPを極めるぞ！！！