代码随想录-算法训练营day53【动态规划14：最长公共子序列、不相交的线、最大子序和(动态规划)】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第九章 动态规划part14
 
● 1143.最长公共子序列 
● 1035.不相交的线   
● 53. 最大子序和  动态规划 
 
 详细布置 
 
 1143.最长公共子序列 
 
体会一下本题和 718. 最长重复子数组 的区别  
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ
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
 
 1035.不相交的线 
 
其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
 
 53. 最大子序和 
 
这道题我们用贪心做过，这次 再用dp来做一遍 
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5
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
 
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR 
●day 31 任务以及具体安排：https://docs.qq.com/doc/DUG1PQ1ZZY2xXY1ly 
●day 32 任务以及具体安排：https://docs.qq.com/doc/DUGFEdGFWeVhleFF1 
●day 33 周日休息 
●day 34 任务以及具体安排：https://docs.qq.com/doc/DUEh5WFVlQkp1U0p4  
●day 35 任务以及具体安排：https://docs.qq.com/doc/DUFRWc3BGRHFXZ1pO  
●day 36 任务以及具体安排：https://docs.qq.com/doc/DUERGbnhhRkFRVENZ 
●day 37 任务以及具体安排：https://docs.qq.com/doc/DUFVRd3p5SHFMSExQ  
●day 38 任务以及具体安排：https://docs.qq.com/doc/DUGNUdVpoT0VJR01l 
●day 39 任务以及具体安排：https://docs.qq.com/doc/DUE55cVJ5WkNoREhS 
●day 40 周日休息
●day 41 任务以及具体安排：https://docs.qq.com/doc/DUFhIUXRFYnVGUkFp 
●day 42 任务以及具体安排：42 第八章 动态规划 
●day 43 任务以及具体安排：43第八章 动态规划 
●day 44 任务以及具体安排：44 第八章 动态规划 
●day 45 任务以及具体安排：45  第八章 动态规划 
●day 46 任务以及具体安排：46 第八章 动态规划 
●day 47 周日休息
●day 48 任务以及具体安排：48 第八章 动态规划 
●day 49 任务以及具体安排：49 第八章 动态规划  
●day 50 任务以及具体安排：50 第八章 动态规划 
●day 51 任务以及具体安排：51 第八章 动态规划 
●day 52 任务以及具体安排：52 第八章 动态规划

目录

1143_最长公共子序列

1035_不相交的线

0053_最大子序和(动态规划)

1143_最长公共子序列

package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;
 
public class _1143_最长公共子序列 {
}
 
class Solution1143 {//二维dp数组
    public int longestCommonSubsequence(String text1, String text2) {
        //char[] char1 = text1.toCharArray();
        //char[] char2 = text2.toCharArray();
        //可以在一开始的时候就先把text1、text2 转成char[]，之后就不需要有这么多为了处理字符串的调整。
        //就可以和卡哥的code更一致
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];//先对dp数组做初始化操作
        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()];
    }
}
 
class Solution1143_2 {//一维dp数组
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        //多从二维dp数组过程分析
        //关键在于 如果记录 dp[i - 1][j - 1]
        //因为 dp[i - 1][j - 1]  <!=>  dp[j - 1]  <=>  dp[i][j - 1]
        int[] dp = new int[n2 + 1];
        for (int i = 1; i <= n1; i++) {
            //这里pre相当于 dp[i - 1][j - 1]
            int pre = dp[0];
            for (int j = 1; j <= n2; j++) {
                //用于给pre赋值
                int cur = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    //这里pre相当于dp[i - 1][j - 1]，千万不能用dp[j - 1] !!
                    dp[j] = pre + 1;
                } else {
                    //dp[j]     相当于 dp[i - 1][j]
                    //dp[j - 1] 相当于 dp[i][j - 1]
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                //更新dp[i - 1][j - 1]，为下次使用做准备
                pre = cur;
            }
        }
        return dp[n2];
    }
}

1035_不相交的线

package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;
 
public class _1035_不相交的线 {
}
 
class Solution1035 {
    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];
    }
}

0053_最大子序和(动态规划)

package com.question.solve.leetcode.programmerCarl2._10_dynamicProgramming;
 
public class _0053_最大子序和 {
}
 
class Solution0053 {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            sum = Math.max(sum, count);//取区间累计的最大值（相当于不断确定最大子序终止位置）
            if (count <= 0) {
                count = 0;//相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
        return sum;
    }
}
 
class Solution0053_2 {
    /**
     * 1.dp[i]代表当前下标对应的最大值
     * 2.递推公式 dp[i] = max (dp[i-1]+nums[i],nums[i]) res = max(res,dp[i])
     * 3.初始化 都为 0
     * 4.遍历方向，从前往后
     * 5.举例推导结果。。。
     *
     * @param nums
     * @return
     */
    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;
    }
}
 
//因为dp[i]的递推公式只与前一个值有关，所以可以用一个变量代替dp数组，空间复杂度为O(1)
class Solution0053_3 {
    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;
    }
}