Menu Close

动态规划解最长子序列子串等一类问题之最长公共子序列[Hog Deer]

hirsch-2015467_960_720.jpg

一些名词

  • 最长上升子序列(LIS):Longest Increasing Subsequence
  • 最长连续序列(LCS):Longest Consecutive Sequence
  • 最长连续递增序列(LCIS):Longest Continuous Increasing Subsequence
  • 最长公共子序列(LCS):Longest Common Subsequence

方法1:DP 基础版

8H6EDO.jpg

  • 对于0位置未添加空字符串

  • dp[i][j]表示的是s1[0...i-1]s2[0...j-1]的最长公共子序列的长度,要求的是dp[m-1][n-1]

  • s1[i]==s2[j],说明这两个字符是公共的字符,只要考察其子问题,dp[i-1][j-1]的长度即可,在此基础上+1,

  • s1[i]!=s2[j],说明这两个字符不是公共的字符,只要考察其两个子问题,dp[i-1][j],dp[i][j-1],取max

  • 动态转移方程:
    <code>dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & \text{s1[i]==s2[j]}\\ max(dp[i-1][j],dp[i][j-1])& \text{s1[i]!=s2[j]} \end{cases}</code>

方法2:DP 优化版

8H2sqf.jpg

  • 对于0位置添加空字符串

  • dp[i][j]表示的是s1[0...i]s2[0...j]的最长公共子序列的长度,要求的是dp[m][n]

  • 注意s1|s2的位置是错位了一个,其长度达不到m|n

方法3:DP压缩空间版O(1)

  • 准备一个dp,n+1的长度,其实的0位置存放一个空字符串

8H0OG6.jpg

8HD96U.jpg

  • 准备几个变量:

    • last:表示是当前dp[j](dp[i][j])左上角的数,相当于dp[i-1][j-1],初始化的时候为0
    • tmp:表示是当前dp[j](dp[i][j])正上方的数,相当于dp[i- 1][j]
    • dp[j-1]:表示是当前dp[j](dp[i][j])左边的数,相当于dp[i][j-1]
    • 每一轮结束后,last的值都向前滚动一个,变成正上方的数,也就是tmp

推荐阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注

苏ICP备20029284号-1