[別解]：「現在の状態」も明示的に持つ動的計画法

本質的には公式解説と同じ DP になりますが、より機械的に実装する方法として、「現在の状態」も DP のキーとして陽に持つと直感的に解きやすいと思います。（一部ではこのテクニックをオートマトンDPや状態DP、耳DPと呼ぶこともあります。）

\[ \begin{aligned} dp[i][j][k] :=\; \text{『}&S\text{ の先頭 }i\text{ 文字までで、} T\text{ の先頭から最大でちょうど }j\text{ 文字まで作れており、}\\ &\text{状態が }k\text{ （選択開始前/途中/終了直後）である場合の数』} \end{aligned} \]

として DP の状態を定義すると、遷移箇所は \(i\) 文字目を選んだか？に応じて次のようにシンプルに書けます。（以降 \(N=|S|,\ M=|T|\) とします。）

for (int j = 0; j <= M; j++) {
    // S[i] を使った後の一致長
    int nj = j + (j < M && S[i] == T[j]);

    // S[i] を選ぶ
    dp[i + 1][nj][1] += dp[i][j][0] + dp[i][j][1];

    // S[i] を選ばない
    dp[i + 1][j][0] += dp[i][j][0];
    dp[i + 1][j][2] += dp[i][j][1];
}

DP テーブルの計算後は、\(j=M,\ k=2\) の状態が「\(T\) を部分列として含み、選択を終えた部分文字列」に対応します。これらと、末尾まで選択中の \(j=M,\ k=1\) の状態を、部分文字列の総数から引けば答えが求まります。（逆に、\(j<M\) の適切な状態だけを足し合わせて答えを直接求めることもできます。）時間計算量は公式解説と同様に \(O(NM)\) です。

[補足]：公式解説との関係

この解法において、\(k=2\) への遷移は \(k=1 → k=2\) の一箇所でしか生じず、その後の遷移もありません。そのため、\(k=2\) を持たず、その場で答えに反映できます。

同様に \(k=0\) も、「各位置から新しい部分文字列を開始する」処理に置き換えれば陽に持つ必要がありません。すると \(k=1\) のみが残り、この状態を明示的に持たなくとも実装できるとわかります。

更に、\(i+1\) の状態は \(i\) の状態のみに依存するため、 \(i\) 次元のキーも持たず、空間計算量を \(O(M)\) に圧縮して実装することも出来ます。この際に、昇順に更新していくと、\(i, i+1\) の \(2\) 本のDP配列を用意する必要がありますが、降順に更新することで \(1\) 本まで抑えると、公式解説の実装へと辿り着きます。