一些名词
- 最长上升子序列(
LIS
):Longest Increasing Subsequence
- 最长连续序列(
LCS
):Longest Consecutive Sequence
- 最长连续递增序列(
LCIS
):Longest Continuous Increasing Subsequence
- 最长公共子序列(
LCS
):Longest Common Subsequence
方法1:DP
基础版
-
对于
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>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public int longestCommonSubsequence(String text1, String text2) { if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0; char[] chas1 = text1.toCharArray(); char[] chas2 = text2.toCharArray(); int m = chas1.length, n = chas2.length; int[][] dp = new int[m][n]; dp[0][0] = chas1[0] == chas2[0] ? 1 : 0; for (int i = 1; i < m; i++) dp[i][0] = chas1[i] == chas2[0] ? 1 : dp[i - 1][0]; for (int j = 1; j < n; j++) dp[0][j] = chas1[0] == chas2[j] ? 1 : dp[0][j - 1]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); if (chas1[i] == chas2[j]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1); } } return dp[m - 1][n - 1]; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: if not text1 or not text2: return 0 m, n = len(text1), len(text2) dp = [[0] * n for _ in range(m)] dp[0][0] = 1 if text1[0] == text2[0] else 0 for i in range(1, m): dp[i][0] = 1 if text1[i] == text2[0] else dp[i - 1][0] for j in range(1, n): dp[0][j] = 1 if text1[0] == text2[j] else dp[0][j - 1] for i in range(1, m): for j in range(1, n): dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) if text1[i] == text2[j]: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1) return dp[m - 1][n - 1] |
方法2:DP
优化版
-
对于
0
位置添加空字符串 -
dp[i][j]
表示的是s1[0...i]
与s2[0...j]
的最长公共子序列的长度,要求的是dp[m][n]
-
注意
s1|s2
的位置是错位了一个,其长度达不到m|n
1 2 3 4 5 6 7 8 9 10 11 12 |
public int longestCommonSubsequence2nd(String text1, String text2) { if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0; int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]); } } return dp[m][n]; } |
方法3:DP
压缩空间版O(1)
- 准备一个
dp
,n+1
的长度,其实的0
位置存放一个空字符串
-
准备几个变量:
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public int longestCommonSubsequence3rd(String text1, String text2) { if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0; int m = text1.length(), n = text2.length(); int[] dp = new int[n + 1]; int tmp = 0; for (int i = 1; i <= m; i++) { int last = 0; for (int j = 1; j <= n; j++) { tmp = dp[j]; if (text1.charAt(i - 1) == text2.charAt(j - 1)) dp[j] = last + 1; else dp[j] = Math.max(tmp, dp[j - 1]); last = tmp; } // System.out.println(JSON.toJSONString(dp)); } return dp[n]; } |