DP查缺补漏之\(LCS\)状态重叠
状态假设
\(F[i][j]\)为\(a\)串中前\(i\)个字符，\(b\)串中前\(j\)个字符构成的\(LCS\)
状态转移
-
\(F[i - 1][j - 1] + 1\)
- 即当且仅当\(a[i] = b[j]\)时，从两个序列的减去当前的字符加一推出
-
\(F[i - 1][j]\)
- 不选\(a[i]\)，只选\(b[j]\)
-
\(F[i][j - 1]\)
- 不选\(b[j]\)，只选\(a[i]\)
-
\(F[i - 1][j - 1]\)
- 不选\(a[i]\)，不选\(b[j]\)
状态重叠
\(F[i - 1][j]\)为例
实际上并非确切的就是不选\(a[i]\)，只选\(b[j]\)的情况，但是这种情况是包含于\(F[i - 1][j]\)，即\(a\)串中前\(i - 1\)个字符，\(b\)串中前\(j\)个字符构成的\(LCS\)中的，而该问题求解最大值，重叠状态并不影响最大值的计算。
代码实现
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
F[i][j] = max(F[i - 1][j], F[i][j - 1]);
if (a[i] == b[j])
{
F[i][j] = max(F[i][j], F[i - 1][j - 1] + 1);
}
}
}