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 保持完整才能求得最终的最大公共长度。

全部评论

相关推荐

哞客37422655...:csol:来了他们来了
点赞 评论 收藏
分享
2025-12-17 12:08
门头沟学院 产品经理
牛客85811352...:1希音不知道算不算大厂 2完全符合,过得很舒服, 3确实只有杂活 领导找我续签到明年3、4月我要继续吗。主要是边实习边秋招这段时间还是有点累
什么是优秀的实习经历
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务