动态规划-1143.最长公共子序列-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 16:59:14

1020

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

一、题目解析

对于给定了两个字符串中，需要找到最长的公共子序列，也就是两个字符串所共同拥有的子序列。

二、算法原理

1、状态表示

dp[i][j]：表示s1的[0,i]和s2的[0,j]区间内所有子序列，最长子序列的长度

2、状态转移方程

根据最后一个位置的状态，分情况讨论

dp[i][j] s1[i]==s2[j]->dp[i-1][j-1]+1

s1[i]!=s2[j]->max(dp[i][j-1],dp[i-1][j])

3、初始化

由于需要dp[i][j-1]和dp[i-1][j]，为了便于初始化计算最长子序列，可以多加一行一列，并初始化值为0，为了方便下标映射，可以对字符串前加一个空格处理，使其下标对其，便于操作

4、填表顺序

为了避免所需值为计算，从上往下，从左往右开始填表

5、返回值

需要返回的是在s1和s2长度下的最长公共子串，所以return dp[m][n]

依旧先画图思考，在自己实现，链接：1143. 最长公共子序列 - 力扣（LeetCode）

三、代码示例

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,0));
        text1 = " "+text1;
        text2 = " "+text2;
        for(int i = 1;i<=m;i++)
        {
            for(int j = 1;j<=n;j++)
            {
                if(text1[i] == text2[j])
                {
                    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];
    }
};