应用商店app下载安装最新版软件,搜索引擎优化缩写,好看的免费的小说网站模板,成都优化网站推广此题我的往期文章推荐#xff1a;
leetCode 1143.最长公共子序列 动态规划 滚动数组-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133689692?spm1001.2014.3001.5501leetCode 1143.最长公共子序列 一步步思考动态规划 优化空间复杂度_呵呵哒(#xf…此题我的往期文章推荐
leetCode 1143.最长公共子序列 动态规划 滚动数组-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133689692?spm1001.2014.3001.5501leetCode 1143.最长公共子序列 一步步思考动态规划 优化空间复杂度_呵呵哒(▽)的博客-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/133702506?spm1001.2014.3001.5501 1S1 和 S2末尾字符相同时那就在 S1前 i-1个字符 与 S2前 j-1个字符 的LCS基础上再加1 2S1 和 S2末尾字符不相同时两种选择方案
把S1的末尾字符抛弃掉计算在 S1前 i-1个字符 与 S2前 j 个字符 的LCS把S2的末尾字符抛弃掉计算在 S1前 i个字符 与 S2前 j-1 个字符 的LCS
比较这两个LCS谁最大就选最大的LCS为最优解 dp[0][0] 表示 S1 前 0 个字符 与 S2 前 0 个字符的 LCS 0 dp[i][0] 表示 S1 前 i 个字符 与 S2 前 0 个字符的 LCS 0 dp[0][j] 表示 S1 前 0 个字符 与 S2 前 j 个字符的 LCS 0 S1A B C B D A BS2B D C A B C
我们可以从这张表格可以得到的信息S1 与 S2 的 最长公共子序列长度为 4且最长公共子序列有BCAB 和 BDAB如下验证
① 最长公共子序列有BCAB
S1A B C B D A BS2B D C A B C
② 最长公共子序列有BDAB
S1A B C B D A BS2B D C A B C
伪代码 可以在力扣运行的代码我在这往期文章里已经写了大家可以移步去看文章链接在此文的首行~
参考B站up主邋遢大哥233做的课堂笔记
[轻松掌握动态规划]5.最长公共子序列 LCS_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1ey4y1d7oD/?spm_id_from333.999.0.0vd_sourcea934d7fc6f47698a29dac90a922ba5a3来自up主邋遢大哥233的课堂截图
