Day45 力扣动态规划 : 1143.最长公共子序列 ｜1035.不相交的线 ｜ 53. 最大子序和

大子序和"/>

Day45 力扣动态规划 : 1143.最长公共子序列 ｜1035.不相交的线 ｜ 53. 最大子序和

Day45 力扣动态规划 : 1143.最长公共子序列 ｜1035.不相交的线 ｜ 53. 最大子序和

• 1143.最长公共子序列
• • 第一印象
  • 看完题解的思路
  • 实现中的困难
  • 感悟
  • 代码
• 1035.不相交的线
• • 第一印象
  • 感悟
  • 代码
• 53. 最大子序和
• • 第一印象
  • • dp
    • 递推公式
    • 初始化
    • 遍历顺序
  • 实现中的困难
  • 感悟
  • 代码

1143.最长公共子序列

体会一下本题和 718. 最长重复子数组 的区别
视频讲解：
.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html

第一印象

这道题就是最长重复子序列的不连续版本了，那道题里我特意明确了一下，重复一定是连续的。

那这道题就不仅仅是dp[i-1][j-1] + 1了，而是找到0～i-1 ，j-1 最大那个了。

这个区别就像最长子序列和最长连续子序列。

我试试

写是写出来了，但是图里的例子就会出现重复的情况：

我的代码是：

class Solution {public int longestCommonSubsequence(String text1, String text2) {//dpint[][] dp = new int[text2.length() + 1][text1.length() + 1];int result = 0;//init//funcfor (int j = 1; j < text1.length() + 1; j++) {for (int i = 1; i < text2.length() + 1; i++) {if (text1.charAt(j - 1) == text2.charAt(i - 1)) {//找前几行for (int m = 0; m < i; m++) {for (int n = 1; n <= j; n++) {dp[i][j] = Math.max(dp[i][j], dp[m][n] + 1);result = Math.max(result, dp[i][j]);}}//找这一行for (int n = 0; n < j; n++) {dp[i][j] = Math.max(dp[i][j], dp[i][n]);result = Math.max(result, dp[i][j]);}}}}for(int i = 0; i < text2.length() + 1; i++)  {for (int j = 0; j < text1.length() + 1; j++) {System.out.print(dp[i][j] + "  ");}System.out.println();}return result;}
}

感觉不能找之前的最大的那个，比如这个c，在dp[3][3]赋值一次变成3之后，又在dp[5][4] 变成 4了，但其实它只应该操作一次。

也就是text1拿来的元素（外层for循环的元素），每次放到text 2 里去遍历一遍，找有没有自己，有的话就要变长。

但是只能找一个自己，因为拿来的一个元素，最多变长一次，也就是+1，不能在for循环中 +1 两次。

//func
for (int j = 1; j < text1.length() + 1; j++) {for (int i = 1; i < text2.length() + 1; i++) {if (text1.charAt(j - 1) == text2.charAt(i - 1)) {//找前几行for (int m = 0; m < i; m++) {for (int n = 1; n <= j; n++) {dp[i][j] = Math.max(dp[i][j], dp[m][n] + 1);result = Math.max(result, dp[i][j]);}}//找这一行for (int n = 0; n < j; n++) {dp[i][j] = Math.max(dp[i][j], dp[i][n] + 1);result = Math.max(result, dp[i][j]);}break;}}
}

这一部分加上break也是错的。如果再text2里找到了这个元素，并且变长结束了，就结束这个元素。去text1里找下一个。

那我直接看题解吧

看完题解的思路

我的思路是不太正确的。

最长递增子序列是，每次都从0看到i-1，如果 i 比 j 大，就尝试更新dp[i] 。

而这道题不太一样，我们要记住dp数组的含义。

长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

所以不会出现dp[i][j] 中间 全是 0 的情况。 比如 1 2 5 和 1 2 7 8

到 2 那里长度是2，到5 和 7 那里长度不该是0，而还是 2.才对

所以要对两个元素不相等的情况赋值，这样两个元素相等的时候，也不需要去找最大的那个长度再 +1 了，可以直接dp[i-1][j-1] + 1。

因为不管前一个是不是相同的，都被赋值了，是相同的就是到 2 那里的长度2.

不是相同的就是， 5 和 7 那里的长度 2.

再有另一个需要注意的就是怎么给不相同的时候赋值。比如 a c b 和 a b e f

I到b，j到e的时候不相同了，按理来说应该返回 长度2，因为ab 和ab是相同的。

但是呢如果你看dp[i-1][j] 是 ac和 abe = 1，dp[i][j-1] 是acb和ab = 2.

所以每次应该取这两个更大的一个。也就是虽然我拿你俩不相同，不能让长度 + 1. 但是这个情况的最长长度，可能是 i 的更长，也可能是 j 的更长。

实现中的困难

思路清晰就不难

感悟

感觉子序列问题真的好难。

我没法举一反三啊

代码

class Solution {public int longestCommonSubsequence(String text1, String text2) {//dpint[][] dp = new int[text1.length() + 1][text2.length() + 1];int result = 0;//init//func//一行一行的去更新for (int i = 1; i < text1.length() + 1; i++) {for (int j = 1; j < text2.length() + 1; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;result = Math.max(result, dp[i][j]);} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return  result;}
}

1035.不相交的线

其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
视频讲解：
.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html

第一印象

我有点想不出来，怎么表示这个线呢。

啊！只有相同元素才会连线，但可能相交。

只有公共子序列，排成了一样的顺序，就不会相交了。

也就是找最大公共子序列。

感悟

悟出来这个，就不用做了，直接改改上一道题的代码了

代码

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {//dpint[][] dp = new int[nums1.length + 1][nums2.length + 1];int result = 0;//init//func//一行一行的去更新for (int i = 1; i < nums1.length + 1; i++) {for (int j = 1; j < nums2.length + 1; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;result = Math.max(result, dp[i][j]);} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return  result;}
}

53. 最大子序和

这道题我们用贪心做过，这次 再用dp来做一遍
视频讲解：
.%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

第一印象

说之前拿贪心做过，我都快忘了。啊，是看sum的效果是buff还是debuff，debuff就重新开始选。

dp的话 我试试先。

我做出来了！！！

dp

以 i 为结尾的连续子数组de最大和是dp[i] 。

递推公式

每次比较 是只有自己更大呢？还是自己 + dp[i-1] 更大呢？

其实也就是，dp[i-1] 放的是之前的最大和，如果这个最大和+nums[i] 和nums[i] 相比是debuff（其实也就是 最大和 < 0 就是debuff），那完全可以从nums[i]开始了，没必要要前面的了。

 //如果是debuff，那么就重新开始吧if (dp[i - 1] < 0) {dp[i] = nums[i];} else {dp[i] = dp[i - 1] + nums[i];}

初始化

dp[0] = nums[0]

遍历顺序

正序

实现中的困难

result 初始化应该是nums[0]

感悟

我太厉害了

代码

class Solution {public int maxSubArray(int[] nums) {//dpint[] dp = new int[nums.length];int result = nums[0];//initdp[0] = nums[0];//funcfor (int i = 1; i < dp.length; i++) {//如果是debuff，那么就重新开始吧if (dp[i - 1] < 0) {dp[i] = nums[i];} else {dp[i] = dp[i - 1] + nums[i];}result = Math.max(result, dp[i]);}return result;}
}