最长公共子序列问题描述样例输入样例输出评测用例规模与约定解析参考程序难度等级问题描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。样例输入text1abcde,text2ace样例输出3评测用例规模与约定1 text1.length, text2.length 1000text1和text2仅由小写英文字符组成。解析分析问题首先就是两个子串找最长公共的序列每个子串的每个字母都可以选或者不选就有2^N2^M次种情况要找到这些情况当中序列相同且最长的时间过于长了普通枚举出所有情况然后比较。但我们可以用别的思想解决问题子串每次到一个字母前面的字母构成了另外一个字串那么再加一个字母是不是就是从之前状态过来的有没有什么关系这就涉及到了动态规划每一步都和之前状态有关系得出这个关系我们就能解决了。怎么得如果到了一个位置ij两个位置的字符相同那么是不是肯定要选上啊和之前的状态就是f [i1][j1]f[i][j]1;如果不相等呢就不用加对不对从哪里开始呢就是f[i-1][j],f[i][j-1]里面挑最大值了。参考程序classSolution{public:intlongestCommonSubsequence(string s,string t){intns.size(),mt.size();vectorf(n1,vectorint(m1));for(inti0;in;i){for(intj0;jm;j){f[i1][j1]s[i]t[j]?f[i][j]1:max(f[i][j1],f[i1][j]);}}returnf[n][m];}};难度等级⭐️⭐️⭐️⭐️1~10星以个人刷题整理为目的如若侵权请联系删除~