一些名词
- 最长上升子序列(
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],初始化的时候为0tmp:表示是当前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]; } |