leetcode 1143. Longest Common Subsequence

目次
标题描述
第一步，明白并理解dp数组及下标的寄义
第二步，分析明白并理解递推公式
第三步，理解dp数组怎样初始化
第四步，理解遍历次序
代码

---

标题描述

这道题和第718题的区别就是，本题求的是最长公共子序列的长度，第718题求的是最长公共子数组的长度。子序列可以不是连续的，子数组则必须是连续的。两道题的分析方法是一样的。
第一步，明白并理解dp数组及下标的寄义

用下标(i-1)遍历text1数组，用下标(j-1)遍历text2数组。
        int len1 = text1.size();
        int len2 = text2.size();
        //i的取值范围是[1,len1]
        //j的取值范围是[1,len2]
        //dp[j]体现字符串text1[0,i-1]和字符串text2[0,j-1]的最长公共【子序列】的长度
按照如许的界说，dp[len1][len2]就是答案。本题dp数组的寄义与第718题不一样。
第二步，分析明白并理解递推公式

 //当i!=0 && j!=0时,分两种环境：
 //如果text1[i-1]==text2[j-1],dp[j]=dp[i-1][j-1]+1
 //如果text1[i-1]!=text2[j-1],dp[j]应该为dp[i-1][j]和dp[j-1]中较大的一个
第三步，理解dp数组怎样初始化

        //dp[0][j]体现text1为空,显然此时text1和text2没有公共【子序列】,dp[0][j]都应该初始化为0
        //dp[0]体现text2为空,显然此时text1和text2没有公共【子序列】,dp[0]都应该初始化为0
        //当i!=0 && j!=0时,分两种环境：
        //如果text1[i-1]==text2[j-1],dp[j]=dp[i-1][j-1]+1,即反面的dp[j]由前面的dp[i-1][j-1]覆盖计算,因此dp[j]可以不初始化，大概为了写代码方便可以统一初始化为0。
        //如果text1[i-1]!=text2[j-1],dp[j]应该为dp[i-1][j]和dp[j-1]中较大的一个,反面的dp[j]由前面的dp[i-1][j]大概前面的dp[j-1]覆盖计算，因此dp[j]可以不初始化，大概为了写代码方便可以统一初始化为0。
第四步，理解遍历次序

由递推公式，可知i和j都应该从小到大遍历。留意i的取值范围是[1,len1]，j的取值范围是[1,len2]。
代码

1. class Solution {
2. public:
3.     int longestCommonSubsequence(string text1, string text2) {
4.         int len1 = text1.size();
5.         int len2 = text2.size();
6.         //i的取值范围是[1,len1]
7.         //j的取值范围是[1,len2]
8.         //dp[i][j]表示字符串text1[0,i-1]和字符串text2[0,j-1]的最长公共【子序列】的长度
9.         //dp[0][j]表示text1为空,显然此时text1和text2没有公共【子序列】,dp[0][j]都应该初始化为0
10.         //dp[i][0]表示text2为空,显然此时text1和text2没有公共【子序列】,dp[i][0]都应该初始化为0
11.         //当i!=0 && j!=0时,分两种情况：
12.         //如果text1[i-1]==text2[j-1],dp[i][j]=dp[i-1][j-1]+1,即后面的dp[i][j]由前面的dp[i-1][j-1]覆盖计算,因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。
13.         //如果text1[i-1]!=text2[j-1],dp[i][j]应该为dp[i-1][j]和dp[i][j-1]中较大的一个,后面的dp[i][j]由前面的dp[i-1][j]或者前面的dp[i][j-1]覆盖计算，因此dp[i][j]可以不初始化，或者为了写代码方便可以统一初始化为0。
14.         vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
15.         for(int i = 1;i <= len1;i++){
16.             for(int j =1;j <= len2;j++){
17.                 if(text1[i-1] == text2[j-1])
18.                 {
19.                     dp[i][j] = dp[i-1][j-1] +1;
20.                 }
21.                 else
22.                 {
23.                     dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
24.                 }
25.             }
26.         }
27.         return dp[len1][len2];
28.     }
29. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。