本节内容
- 1143.最长公共子序列
- 1035.不相交的线
- 最大子序和
1143.最长公共子序列※
建议：
题目链接： https://leetcode.cn/problems/longest-common-subsequence/
文章讲解： https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
视频讲解：
题目分析
方案一
此题和 718. 最长重复子数组 十分相似！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[] dp = new int[text1.length()];
int result = 0;
for (int i = 0; i < text2.length(); i++) {
for (int j = text1.length() - 1; j >= 0; j--) {
if (text2.charAt(i) == text1.charAt(j)) {
dp[j] = 1;
for (int k = 0; k < j; k++) {
dp[j] = Math.max(dp[j], dp[k] + 1);
}
result = Math.max(result, dp[j]);
}
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:1190 ms,击败了5.26% 的Java用户
内存消耗:39.3 MB,击败了98.84% 的Java用户
分析
时间复杂度：
O( n ^ 2 * m )
空间复杂度：
O( n )
降低一下时间复杂度
看完题解之后的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1; i <= text1.length(); i++) {
for (int j = 1; j <= text2.length(); 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 - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
|
结果
解答成功:
执行耗时:23 ms,击败了26.89% 的Java用户
内存消耗:47.5 MB,击败了14.33% 的Java用户
分析
时间复杂度：
O( n * m )
空间复杂度：
O( n + m )
代码随想录
https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
思路
本题和 718. 最长重复子数组 区别在于这里不要求是连续的了，但要有相对顺序，即：”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
继续动规五部曲分析如下：
- 确定dp数组（dp table）以及下标的含义
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？
这样定义是为了后面代码实现方便。
- 确定递推公式
主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
代码如下：
1
2
3
4
5
| 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]);
}
|
- dp数组如何初始化
先看看dp[i][0]应该是多少呢？
test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
同理dp[0][j]也是0。
其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。
代码：
1
| vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
|
- 确定遍历顺序
从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。
- 举例推导dp数组
以输入：text1 = “abcde”, text2 = “ace” 为例，dp状态如图：
最后红框dp[text1.size()][text2.size()]为最终结果
以上分析完毕，C++代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); j++) {
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[text1.size()][text2.size()];
}
};
|
- 时间复杂度: O(n * m)，其中 n 和 m 分别为 text1 和 text2 的长度
- 空间复杂度: O(n * m)
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1 ; i <= text1.length() ; i++) {
char char1 = text1.charAt(i - 1);
for (int j = 1; j <= text2.length(); j++) {
char char2 = text2.charAt(j - 1);
if (char1 == char2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length();
int n2 = text2.length();
int [] dp = new int[n2 + 1];
for(int i = 1; i <= n1; i++){
int pre = dp[0];
for(int j = 1; j <= n2; j++){
int cur = dp[j];
if(text1.charAt(i - 1) == text2.charAt(j - 1)){
dp[j] = pre + 1;
} else{
dp[j] = Math.max(dp[j], dp[j - 1]);
}
pre = cur;
}
}
return dp[n2];
}
}
|
1035.不相交的线※
建议：
题目链接： https://leetcode.cn/problems/uncrossed-lines/
文章讲解： https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
视频讲解：
题目分析
方案一
解题方案不能说与 1143.最长公共子序列 、 718. 最长重复子数组 有多大区别，只能说一模一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[] dp = new int[nums1.length];
int result = 0;
for (int i = 0; i < nums2.length; i++) {
for (int j = nums1.length - 1; j >= 0; j--) {
if (nums2[i] == nums1[j]) {
dp[j] = 1;
for (int k = 0; k < j; k++) {
dp[j] = Math.max(dp[j], dp[k] + 1);
}
result = Math.max(result, dp[j]);
}
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:3 ms,击败了99.72% 的Java用户
内存消耗:39.5 MB,击败了97.56% 的Java用户
分析
时间复杂度：
O( n ^ 2 * m )
空间复杂度：
O( n )
尝试优化一下时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for (int i = 1; i <= nums1.length; i++) {
for (int j = 1; j <= nums2.length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[nums1.length][nums2.length];
}
}
|
结果
解答成功:
执行耗时:4 ms,击败了98.98% 的Java用户
内存消耗:42.2 MB,击败了6.61% 的Java用户
分析
时间复杂度：
O( n * m )
空间复杂度：
O( n + m )
代码随想录
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
思路
相信不少录友看到这道题目都没啥思路，我们来逐步分析一下。
绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
拿示例一A = [1,4,2], B = [1,2,4]为例，相交情况如图：
其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）
这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
那么本题就和我们刚刚讲过的这道题目 1143.最长公共子序列 就是一样一样的了。
一样到什么程度呢？ 把字符串名字改一下，其他代码都不用改，直接copy过来就行了。
其实本题就是求最长公共子序列的长度，介于我们刚刚讲过 1143.最长公共子序列 ，所以本题就不再做动规五部曲分析了。
本题代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[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[A.size()][B.size()];
}
};
|
- 时间复杂度: O(n * m)
- 空间复杂度: O(n * m)
总结
看到代码大家也可以发现其实就是求两个字符串的最长公共子序列，但如果没有做过 1143.最长公共子序列 ，本题其实还有很有难度的。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[len1][len2];
}
}
|
53. 最大子序和※
建议：
题目链接： https://leetcode.cn/problems/maximum-subarray/
文章讲解： https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
视频讲解：
题目分析
方案一
曾经在贪心算法中做过本题目： # 53. 最大子序和
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxSubArray(int[] nums) {
int result = nums[0];
int dp = nums[0];
for (int i = 1; i < nums.length; i++) {
dp = Math.max(nums[i], dp + nums[i]);
result = Math.max(dp, result);
}
return result;
}
}
|
结果
解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:56.4 MB,击败了36.28% 的Java用户
分析
时间复杂度：
O( n )
空间复杂度：
O( 1 )
代码随想录
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
思路
这道题之前我们在讲解贪心专题的时候用贪心算法解决过一次
这次我们用动态规划的思路再来分析一次。
动规五部曲如下：
- 确定dp数组（dp table）以及下标的含义
**dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]**。
- 确定递推公式
dp[i]只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
- dp数组如何初始化
从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
dp[0]应该是多少呢?
根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。
- 确定遍历顺序
递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
- 举例推导dp数组
以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。
在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。
那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。
所以在递推公式的时候，可以直接选出最大的dp[i]。
以上动规五部曲分析完毕，完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > result) result = dp[i];
}
return result;
}
};
|
总结
这道题目用贪心也很巧妙，但有一点绕，需要仔细想一想。
动规的解法还是很直接的。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public static int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
res = res > dp[i] ? res : dp[i];
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int pre = nums[0];
for(int i = 1; i < nums.length; i++) {
pre = Math.max(pre + nums[i], nums[i]);
res = Math.max(res, pre);
}
return res;
}
}
|