以下では 「\(S\) の \(1\) 文字目から \(a\) 文字目までを取り出した部分列」を \(S_a\) のように表します。
二次元 DP テーブル \(dp_{a, b}\) を次のように定めます。

• \(dp_{a,b} := \) \(S_a\) と \(T_b\) の最長非共通部分列の長さ

\(S_a\) と \(T_b\) の最長非共通部分列の組を \(U_{a,b}\) と表します。 \(U_{a,b}\) がどのような構造を取っているかを考えてみましょう。
\(S\) の \(a\) 文字目を \(S[a]\) と表して場合分けを行います。

• \(S[a], T[b]\) を両方使う場合

まず、両方を使用する場合は \(S[a]\) と \(T[b]\) がともに末尾にくることから、 \(S[a] \neq T[b]\) を満たす必要があります。
この場合、部分列の性質より、求めたい列の組から \(S[a]\) と \(T[b]\) を取り除いたものは \(U_{a-1,b-1}\) として条件を満たす必要があります。ここから、 両方使う場合の最長非共通部分列の長さは \(dp_{a-1,b-1} + 1\) になることがわかります。

• \(S[a], T[b]\) の少なくとも片方を使わない場合

どちらか一方を使わない場合、最長非共通部分列の組は \(U_{a-1,b}\) または \(U_{a,b-1}\) である必要があります。よって長さは \(dp_{a-1,b}\) または \(dp_{a,b-1}\) となります。

上記の場合分けの中であり得る文字列のうち最長のものが \(dp_{a,b}\) の値になります。 \(dp_{a,b}\) は \(\mathrm{O}(1)\) で計算できるので、この問題を \(\mathrm{O}(|S||T|)\) で解くことができました。
実装上は \(a = 1\) や \(b=1\) の場合に適切な場合分けを入れる必要があるのに注意してください。

ちなみに、この問題は最長共通部分列 (Longest Common Subsequence) と同様のアルゴリズムを問うた問題です。

C++ による実装例は次の通りです。(解説とは異なり 0-indexed で実装してるので off-by-one error に注意してください。)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  string S, T;
  cin >> S >> T;
  int N = S.size();
  int M = T.size();
  vector dp(N + 1, vector(M + 1, 0));
  auto chmax = [&](int &x, int y) { x = max(x, y); };
  rep(i, N + 1) {
    rep(j, M + 1) {
      if (i != N) chmax(dp[i + 1][j], dp[i][j]);
      if (j != M) chmax(dp[i][j + 1], dp[i][j]);
      if (i != N and j != M and S[i] != T[j]) {
        chmax(dp[i + 1][j + 1], dp[i][j] + 1);
      }
    }
  }
  cout << dp[N][M] << "\n";
}