AtCoder Educational DP Contest F問題解いてみた

今回の問題

問題文

文字列 $s$ および $t$ が与えられます。 $s$ の部分列かつ $t$ の部分列であるような文字列のうち、最長のものをひとつ求めてください。

注釈

文字列 $x$ の部分列とは、$x$ から $0$ 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。

制約

• $s$ および $t$ は英小文字からなる文字列である。
• $1 \le |s|, |t| \le 3000$

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    string s ;
    cin >> s;
    string t;
    cin >> t;
    int slen = s.length();
    int tlen = t.length();
    int dp[slen+1][tlen+1];
    for(int i = 0; i <= slen; i++) {
        for(int j = 0; j <= tlen; j++) {
            dp[i][j] = 0;
        }
    }
    for(int i = 1; i <= slen; i++) {
        for(int j = 1; j <= tlen; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(s[i-1] == t[j-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    string ans;
    int i = slen;
    int j = tlen;
    while(i > 0 && j > 0) {
        if(dp[i][j] == dp[i-1][j]) {
            i--;
        } else if(dp[i][j] == dp[i][j-1]) {
            j--;
        } else {
            ans += s[i-1];
            i--;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;   
    return 0;
}

解説

dp[i][j]はsのi-1文字目まで、tのj-1文字目までの最長なものの長さとする。sのi-1文字目、tのj-1文字目が同じだったらそれを使う。また、使わないときはmax(dp[i][j-1],dp[i-1][j])となる。最後に、dpの表をさかのぼることによって答えを得る。直前がどことどこであってるかがわかればほかの情報は必要ない。
今回ももらうdpで書いた。