对于这个状态转移方程。为何当ai不等于b时j,不用考虑f(i,j)等于f(i,j-1)一的情况?
谢谢各位大佬们了
当 a[i] != b[j] 时, 因为 F[i,j] 是以 b[j] 为结尾的LCS,如果 F[i,j] > 0 那么就说明 a[1]..a[i] 中必然有一个整数 a[k] 等于 b[j] ,因为 a[k] != a[i] ,那么 a[i] 对 F[i,j] 没有贡献,于是我们不考虑它照样能得出 F[i][j] 的最优值。所以在 a[i] != b[j] 的情况下有 F[I,j] == F[i-1,j] 。