アルゴリズム道中記〜最長共通部分列〜

A20 - LCS

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
using namespace std;
using ll = long long;

int main() {
  string S, T;
  cin >> S >> T;
  S.insert(0, " "); T.insert(0, " ");
  vector<vector<int>> dp(T.size(), vector<int>(S.size()));
  rep (i, 1, T.size())
  {
    rep (k, 1, S.size())
    {
      if (T[i] == S[k])
      {
        dp[i][k] = max(
            dp[i-1][k],
            max(
              dp[i][k], dp[i-1][k-1]+1
              )
            );
      }
      else
        dp[i][k] = max(dp[i-1][k], dp[i][k-1]);
    }
  }
  print(dp[T.size()-1][S.size()-1]);
}

全くもってわからない問題でした。結局、

[鉄則A20] LCS (最長共通部分列)

上のコードを拝見し、それを実装しました。ただ、それだけでは悔しいですので、一度まっさらな状態で一からもう一回コードを書きました。