代码随想录刷题|LeetCode 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划

简介: 代码随想录刷题|LeetCode 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 动态规划

1143.最长公共子序列

题目链接:力扣

思路


 不知道为什么,子序列问题的动态规划感觉比 背包问题 和 买卖股票问题 这两类题目难理解很多,比较了以下,可能是因为之前的数组,横列数列代表的都是不同的东西,而序列问题横列和数列代表的都是字符串本身,可能是这个原因吧,还不太清楚


       可以看一下这个视频的图表推导:对照着代码更容易理解:最长公共子序列


1、确定dp数组

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


2、确定递推公式

两种情况:


text1[ i ] 与 text2[ j ]相同

那就是找到了一个公共元素,所以:dp[ i ][ j ] = dp[i - 1][j - 1] + 1;


text1[ i ] 与 text2[ j ]不相同

那就要看看长度为[0, i - 1]的text1与长度为[0 , i]的text2 的最长公共子序列

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

              这两个哪个最大,取最大的


a78b4497200947569591ec2f6c7c07a4.png


所以:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

最终的代码就为


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]);
}

3、dp数组初始化

dp[i][0] 表示:长度为[0, i ]的text1 与 空串的最长公共子序列,那肯定是 0 ,所以dp[i][0] = 0;


同理:dp[0][j] = 0


其他的会根据上面的一列一行,计算覆盖,所以赋值什么都可以的,所以统一默认为0 就行


895227804d3847ad8991fbd0f5091248.png


4、遍历顺序

从前向后遍历


5、推导dp数组


1c96f391d613487eb0e76aa36c349b3c.png


       dp数组的 行和列 是比两个字符串的长度多1的,这是一个面对代码不太好理解的点


       所以在遍历字符串的时候都是从1开始,求的第一个其实就是 dp[1][1] ,但是此时是根据初始化的那部分来求的,此时是字符串以下标的 0 和 0 结尾的字符串,但是是dp数组的[1][1]


91b465426f794dedaa2bdb0ac2c6893b.png

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 创建dp数组
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        // 初始化dp数组
        // 默认就是初始化
        // 推导dp数组
        for (int i = 1; i <= text1.length(); i++) {
            char chi = text1.charAt(i - 1);
            for (int j = 1; j <= text2.length(); j++) {
                char chj = text2.charAt(j - 1);
                if (chi == chj) {
                    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[text1.length()][text2.length()];
    }
}

1035.不相交的线

题目链接:力扣

思路

这道题目是求不相交的线,其实就是求两个数组的最长公共子序列,这样就跟上一道题目一样了,一模一样的代码,就是把字符串换成了数组

不相交的线

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 创建dp数组
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        // 初始化dp数组
        // 推导dp数组
        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][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}

53. 最大子序和

题目链接:力扣

思路


 看起来简单,自己写了一下,还是有不少细节的,只要是初始化和result的赋值 ,如果摸不准就在推导完dp数组后在选取最大值


1、确定dp数组的含义


dp[i]:包括下标i之前的最大连续子序列和为dp[i]


2、确定递推公式


做过贪心算法的方法就很容易理解,有两种情况


dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和

nums[i],即:从头开始计算当前连续子序列和

3、初始化


从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态,dp[0]就是递推公式的基础。


dp[0]应为nums[0]即dp[0] = nums[0]


4、遍历顺序


从前向后进行遍历


最大子序列

动态规划

// 在推导dp数组的过程中获取最大值
class Solution {
    public int maxSubArray(int[] nums) {
        // 创建dp数组
        int[] dp = new int[nums.length];
        // 初始化dp数组
        dp[0] = nums[0];
        // 推导dp数组
        // 获取结果
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i],dp[i - 1] + nums[i]);
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return  result;
    }
}
// 推导完dp数组后再获取最大值
class Solution {
    public int maxSubArray(int[] nums) {
        // 创建dp数组
        int[] dp = new int[nums.length];
        // 初始化dp数组
        dp[0] = nums[0];
        // 推导dp数组
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(nums[i],dp[i - 1] + nums[i]);
        }
        // 获取结果
        int result = Integer.MIN_VALUE;
        for (int num : dp) {
            result = num > result ? num : result;
        }
        return result;
    }
}

贪心算法

class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            if (count > result) {
                result = count;
            }
            if (count < 0) {
                count = 0;
            }
        }
        return result;
    }
}
相关文章
|
4月前
|
Python
【Leetcode刷题Python】1143. 最长公共子序列
LeetCode 1143题 "最长公共子序列" 的Python解决方案,使用动态规划算法计算两个字符串的最长公共子序列长度。
47 1
【Leetcode刷题Python】1143. 最长公共子序列
|
6月前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
40 1
|
6月前
力扣-2029-石子游戏-‘屎山’代码
力扣-2029-石子游戏-‘屎山’代码
44 3
|
6月前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
53 0
|
6月前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
34 0
|
6月前
|
算法
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学
46 0
|
6月前
|
机器人
【LeetCode】--- 动态规划 集训(二)
【LeetCode】--- 动态规划 集训(二)
42 0
|
6月前
【LeetCode】--- 动态规划 集训(一)
【LeetCode】--- 动态规划 集训(一)
36 0
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
6月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总