【算法|动态规划No.14】leetcode1143. 最长公共子序列

点击直接跳转到该题目

1️⃣题目描述

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

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

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例1：

示例2：

示例3：

注意：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

2️⃣题目解析

状态表示：

• dp[i][j]表示字符串text1区间[0,i]和字符串text2区间[0,j]中所有公共子序列中，最长公共子序列的长度。

状态转移方程（分为两种情况）这里我创建了虚拟节点，所以多开辟了一块空间，大家一定要注意下标的映射关系：

• if(text1[i] == text[j])，则dp[i][i] = dp[i-1][j-1] + 1
• if(text1[i] != text[j])I，则dp[i][j] = max(dp[i][j-1] , dp[i-1][j])

填表顺序：

• 根据状态转移方程我们可以知道填表顺序应该是从上到下、从左往右的。

返回值(m和n分别表示两个字符的长度)：

• dp[m][n]

3️⃣解题代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(),n = text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i = 1;i <= m;i++)
        {
            for(int j = 1;j <= n;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[m][n];
    }
};

最后就是通过啦！！！