LeetCode 1143 最长公共子序列

1143.最长公共子序列

给定两个字符串 text1 和 text2 ，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

动态规划

本题也是一个求解最长公共子序列的问题，但是不同于718.最长重复子数组，在本题中的子序列是不连续的，那么使用动态规划进行求解，就需要改变动态规划数组的定义。

1. 动态规划数组的定义：定义数组 dp[text1.size()+1][text2.size()+1] ，其中 dp[i][j] 表示在 text1[i-1] 和 text2[j-1] 前的最长子序列的长度

2. 动态规划数组的推导：对于 dp[i][j] ，那么首先需要判断 text1[i-1]==text2[j-1] ，不相等 dp[i][j]=max(dp[i-1][j],dp[i][j-1]) （也就是等于两个更短序列的最长的公共子序列的长度，更短的方式有两种，分别是缺少 text1[i-2] 和 text2[j-2] ），若是相等， dp[i][j]=dp[i-1][j-1]+1 ，相等则是在 text1[i-2] 和 text2[j-2] 的基础上在增加一个长度值。

3. 动态规划数组的初始化：在初始时只需要全部初始化为0即可。

4. 动态规划数组的遍历：逐行遍历，在行内采取从前向后的遍历方式。

5. 举例验证：对于 text1 = "abcde", text2 = "ace" 对应的动态规划数组为：

0,0,0,0,
0,1,1,1,
0,1,1,1,
0,1,2,2,
0,1,2,2,
0,1,2,3,

代码实现：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size()+1,m=text2.size()+1;
        vector<vector<int>> dp(n,vector<int>(m,0));
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(text1[i-1]==text2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n-1][m-1];
    }
};