题解 | #最长公共子序列(二)#

最长公共子序列问题 + 输出序列

如何输出序列？

根据状态数组从后往前反推序列中的每个字母

1. 如果 $f[i-1][j-1]->f[i][j]f[i\; -\; 1][j\; -\; 1]\; ->\; f[i][j]$（$f[i][j]f[i][j]$ 这个状态是从 $f[i-1][j-1]f[i\; -\; 1][j\; -\; 1]$ 传递而来），则 $s1[i-1]==s2[j-1]s1[i\; -\; 1]\; ==\; s2[j\; -\; 1]$，所以当前字母一定在子序列中，把 $s[i-1]s[i\; -\; 1]$ 加入到答案中且下标 i -- , j -- 继续往前寻找。
2. 如果 $f[i-1][j]->f[i][j]f[i\; -\; 1][j]\; ->\; f[i][j]$（$f[i][j]f[i][j]$ 这个状态是从 $f[i-1][j]f[i\; -\; 1][j]$ 传递而来），说明 $f[i-1][j]>f[i][j-1]f[i\; -\; 1][j]\; >\; f[i][j\; -\; 1]$，下标 i -- 继续往前寻找。
3. 否则 $f[i][j-1]->f[i][j]f[i][j\; -\; 1]\; ->\; f[i][j]$（$f[i][j]f[i][j]$ 这个状态是从 $f[i][j-1]f[i][j\; -\; 1]$ 传递而来），说明 ，下标 j -- 继续往前寻找。（经测试这里 = 的情况放在情况 2 中也同样正确，看到其他人的代码都放在了这里）

最后将答案字符串翻转