百度提前批二面

今天主要是最长公共子序列 和 判断子序列这两类问题的区分。在公共子序列问题中有不相等的时候 dp[i][j]=max(dp[i-1][j],dp[i][j-1])和子系列不相等的时候却是 dp[i][j] = dp[i][j-1] 因为判断子系列问题是给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 实际上我们转换的问题是s 字符串在在 t 字符串中最长距离。 因此不相等的时候要保持 s 字符串的完整在公共子序列问题中我们求得是 s 和 t 中最大的公共长度，无法确保当前是 s 保持完整还是 t 保持完整才能求得最终的最大公共长度。