题目给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。示例 1输入text1 “abcde”, text2 “ace”输出3解释最长公共子序列是 “ace” 它的长度为 3 。示例 2输入text1 “abc”, text2 “abc”输出3解释最长公共子序列是 “abc” 它的长度为 3 。示例 3输入text1 “abc”, text2 “def”输出0解释两个字符串没有公共子序列返回 0 。思路对于要找出最大最小且需要对比两个字符串的时候可以尝试从结果倒推如果发现可以将问题分解为同样的子问题时尝试使用dp找出条件画出dp表。这题要找出最长公共子序列尝试从后往前倒推发现可以分为两种情况text1和text2的字符相同text1和text2的字符不同对于不同的情况发现可以找到它的前一个状态依旧有两种情况因此使用dp。接下来使用二维dp画出状态表令word1为横轴word2为纵轴最左上角为两个字符串为空。第一行和第一列的边界条件均为0因为没有相同的字符。那么对于其他的dp[j][i]:如果text1和text2的字符相同,那么dp等于左上方的状态1如果不同,那么分为两种情况:求word1[i-1]和word2[j]的最长公共子序列,即从左边的状态转移过来求word1[i]和word2[j-1]的最长公共子序列,即从上方的状态转移过来这两种情况种取较大一方的状态更新dp表“”word1“”000000w0o0r0dp[j][i]d020res最终的结果即状态表最右下的值代码class Solution{public: int longestCommonSubsequence(string text1, string text2){intres0;intcnt20;for(inti0;itext1.size();i){for(intjcnt2;jtext2.size();j){if(text1[i]text2[j]){res;cnt2j1;break;}}}returnres;}};这道题目跟编辑距离很像,都是二维dp,现在知道思路以后就可以立马编写出来代码了感谢 华南溜达虎 力扣 blind75