经典动态规划：最长公共子序列
source link: https://labuladong.github.io/algo/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/LCS.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
详解最长公共子序列问题，秒杀三道动态规划题目
👆让天下没有难刷的算法！若 GitBook 访问太慢，可尝试 GiteePages 或 GitHubPages！
相关推荐：
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
好久没写动态规划算法相关的文章了，今天来搞一把。
不知道大家做算法题有什么感觉，我总结出来做算法题的技巧就是，把大的问题细化到一个点，先研究在这个小的点上如何解决问题，然后再通过递归/迭代的方式扩展到整个问题。
比如说我们前文 手把手带你刷二叉树第三期，解决二叉树的题目，我们就会把整个问题细化到某一个节点上，想象自己站在某个节点上，需要做什么，然后套二叉树递归框架就行了。
动态规划系列问题也是一样，尤其是子序列相关的问题。本文从「最长公共子序列问题」展开，总结三道子序列问题，解这道题仔细讲讲这种子序列问题的套路，你就能感受到这种思维方式了。
最长公共子序列
计算最长公共子序列（Longest Common Subsequence，简称 LCS）是一道经典的动态规划题目，大家应该都见过：
给你输入两个字符串 s1 和 s2，请你找出他们俩的最长公共子序列，返回这个子序列的长度。
力扣第 1143 题就是这道题，函数签名如下：
int longestCommonSubsequence(String s1, String s2);
比如说输入 s1 = "zabcde", s2 = "acez"，它俩的最长公共子序列是 lcs = "ace"，长度为 3，所以算法返回 3。
如果没有做过这道题，一个最简单的暴力算法就是，把 s1 和 s2 的所有子序列都穷举出来，然后看看有没有公共的，然后在所有公共子序列里面再寻找一个长度最大的。
显然，这种思路的复杂度非常高，你要穷举出所有子序列，这个复杂度就是指数级的，肯定不实际。
正确的思路是不要考虑整个字符串，而是细化到 s1 和 s2 的每个字符。前文 子序列解题模板 中总结的一个规律：
＿＿＿＿＿＿＿＿＿＿＿＿＿
本文只能在 labuladong 公众号查看，关注后可直接搜索本站内容：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK