算法第三十二天-最长公共子序列

最长公共子序列

题目要求

解题思路

求这两个数组或者字符串的最长公共子序列问题，肯定要用到动态规划。

• 首先区分两个概念：子序列可以是不连续的；子数组（子字符串）是需要连续的；
• 另外，动态规划也是需要套路的：单个数组或者字符串要用动态规划时，可以把动态规划dp[i]定义为num[0:i]中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成二维的dp[i][j]，其含义是在A[0:i]和B[0:j]之间匹配得到的想要的结果。

  1.状态定义

  比如对于本题而言，可以定义dp[i][j]表示text1[0:i-1]和text2[0:j-1]的最长公共子序列。

  之所以dp[i][j]的定义不是text1[0:i]和text2[0:j]，是为了方便当i=0或者j=0的时候，dp[i][j]表示的为空字符串和另外一个字符串的匹配，这样子dp[i][j]可以初始化为0.

  2.状态转移方程

  知道状态定义之后，我们开始写状态转移方程。

  • 当text1[i-1]==text2[j-1]时，说明两个字符串的最后一位不相等，那么此时的状态dp[i][j]应该是dp[i-1][j]和dp[i][j-1]的最大值。举个例子，比如对于ace和bc而言，它们的最长公共子序列的长度等于①ace和b的最长公共子序列长度0与②ac和bc的最长公共子序列长度1的最大值，即1.

    综上，状态转移方程为：

  • dp[i][j]=dp[i-1][j-1]+1，当text1[i-1]==text[j-1];
  • dp[i][j]=max(dp[i-1][j],dp[i][j-1])，当text1[i-1]!=text2[j-1]

    3.状态的初始化

    初始化就是要看当i=0与j=0时，dp[i][j]应该取值为多少；

    • 当i=0时，dp[0][j]表示的时text1中取空字符串跟text2的最长公共子序列，结果肯定为0；
    • 当j=0时，dp[i][0]表示的是text2中取空字符串跟text1的最长公共子序列，结果肯定为0

      综上，当i=0或者j=0时，dp[i][j]初始化为0

      4.遍历方向与范围

      由于dp[i][j]依赖于dp[i-1][j-1]，dp[i-1][j]，dp[i][j-1]，所以i和j的遍历顺序肯定是从小到大的。

      另外，由于当i和j取值为0的时候，dp[i][j]=0，而dp数组本身初始化就是为0，所以，直接让i和j从1开始遍历。遍历的结束应该是字符串的长度为len(text1)和len(text2)

      5.最终返回结果

      由于dp[i][j]的含义是text1[0:i-1]和text2[0:j-1]的最长公共子序列。所以需要返回的结果是i=len(text1)并且j=len(text2)时的dp[len(text1)][len(text2)]

      代码

      class Solution:
          def longestCommonSubsequence(self, text1: str, text2: str) -> int:
              M=len(text1)
              N=len(text2)
              dp=[[0]*(N+1)  for _ in range(M+1)]
              for i in range(1,M+1):
                  for j in range(1,N+1):
                      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]
      

      复杂度分析

      时间复杂度： O ( M N ) O(MN) O(MN)

      空间复杂度： O ( M N ) O(MN) O(MN)