【最长公共子序列】

最长公共子序列

• • 题目描述：
  • • 解题思路：动态规划
    • 代码

题目描述：

• 链接: 1143. 最长公共子序列.
  

解题思路：动态规划

• dp[i][j] 表示什么？
  定义 dp[i][j]表示字符串dp[i][j] 表示text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。
  

  
  

• 初始状态：
  当 i=0 时，text1[0:i] 为空，空字符串和任何字符串的最长公共子序列的长度都是0，
  因此对任意 0 ≤ j ≤ n，有 dp[0][j]=0；
  同理： 对任意 0 ≤ i≤ m，dp[i][0]=0。
  

  
  

  
  动态规划的边界情况是：当 i=0 或 j=0 时，dp[i][j]=0。
  

  
  

• 状态转移方程：
  当 i>0且 j>0 时，考虑dp[i][j] 的计算：
  当 text1[i-1]=text2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1
  当 text1[i-1] ！= text2[j-1]时，考虑
  ① text1[0:i−1] 和text2[0:j] 的最长公共子序列；
  ② text1[0:i] 和text2[0:j-1] 的最长公共子序列；
  取两者最大值

代码

• Python3

#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:2022—04-04
# author:wupke

from matplotlib.pyplot import text

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n = len(text1),len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]  # 创建 m+1 行 n+1 列的二维数组
        for i in range(1,m+1): # 从1开始，当 i = 0 或者 j = 0 时，dp[i][j] 初始化为 0.
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1  # 状态转移方程 1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])  # 状态转移方程 2
        return dp[m][n] # 返回值

# 时间复杂度：O(mn)二维数组 dp 有 m+1 行 n+1 列 ，对每个元素进行计算
# 空间复杂度 O(mn)：创建了 m+1 行 n+1 列的二维数组 dp。


if __name__=="__main__":
    s = Solution()
    text1 = "abcdefghijk"
    text2 = "afgde"

    res = s.longestCommonSubsequence(text1,text2)

    print("res",res)

• c++

/*************************************************
** 
* Code description:
* time:2022—04-04
* author:wupke
*
***************************************************/
#include 
#include 
#include 
#include 

class Solution {
public:
    int longestCommonSubsequence(std::string text1, std::string text2) {
        int m = text1.size(), n = text2.size();
        std::vector<std::vector<int> > dp(m+1,std::vector<int>(n+1,0)); // 创建 m+1 行 n+1 列的二维数组 (边界条件初始化为0)
         for(int i=1; i<=m; i++ ){
             for (int j=1; j<=n; j++){
                 if (text1[i-1] == text2[j-1]){  //状态转移方程 情况1
                     dp[i][j] = dp[i-1][j-1] +1;
                 }
                 else{
                     dp[i][j] = std::max(dp[i-1][j],dp[i][j-1]);//状态转移方程 情况2
                    }
             }
         }

    return dp[m][n];
    }
};

int main(){
    Solution solve;
    std::string t1 = "abcdef";
    std::string t2 = "abcf";
    printf("%d\n",solve.longestCommonSubsequence(t1,t2));
    return 0;
}