day44 | 子序列问题
今天主要是
最长公共子序列 和 判断子序列这两类问题的区分。
在公共子序列问题中有不相等的时候 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 保持完整才能求得最终的最大公共长度。
投递美团等公司8个岗位 >