动态规划Day14(子序列第二天)

这篇具有很好参考价值的文章主要介绍了动态规划Day14(子序列第二天)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1143.最长公共子序列

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难

1035.不相交的线

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难

53. 最大子序和

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难


1143.最长公共子序列

力扣题目链接(opens new window)

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 1:

  • 输入:text1 = "abcde", text2 = "ace"
  • 输出:3
  • 解释:最长公共子序列是 "ace",它的长度为 3。

示例 2:

  • 输入:text1 = "abc", text2 = "abc"
  • 输出:3
  • 解释:最长公共子序列是 "abc",它的长度为 3。

示例 3:

  • 输入:text1 = "abc", text2 = "def"
  • 输出:0
  • 解释:两个字符串没有公共子序列,返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符
看到题目的第一想法
               

        用动态规划,dp[][]为二维数组

        dp的定义:dp[i][j] ,nums1 的[0,i-1],  nums2的[0,j-1] 的最长公共子序列的长度

        递推公式

        我的递推公式有错,我想着是再遍历i和j,把所有和加起来最大值替代dp[i][j],其实是没有结合dp数组的定义来写dp的递推公式

        

看到代码随想录之后的想法

        用动态规划

        确定dp数组和每个下标的含义

        dp[i][j]记录末尾为i-1和j-1的最长的子序列的长度

        

        确定递推公式

        要从递推公式来进行考虑

       若text1[i] = text2[j] 则在之前的基础上+1

                dp[i][j] = dp[i-1][j-1]+1; 

        若text1[i] != text2[j] 则等于之前的最大值 

                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

         dp数组初始化

                  因为dp[i][j] 代表0~i-1,0~j-1的最大子序列,则不需要定义dp[i][0],dp[0][j],因为0 代表-1没有意义

        确定遍历顺序

        从前往后,从上往下

        举例推导dp数组           

        打印dp数组

        打印最后一个元素

自己实现过程中遇到的困难

       自己需要注意i-1和j-1这个点,同时for循环的条件需要 i<=  j<=  不要忘了等号

        要结合dp的定义来写递推公式

        字符串用char[] 比较好写

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //二维数组?dp[i][j]记录text1下标i到text2下标j的长度
        //上一题是连续,这一题不连续
        //dp[i][j]后遍历 若 text1[i] = text2[j]
        //则遍历到i,j,不断更新dpij的最大值
        //text1 text2
        /*int[][] dp = new int[text1.length()+1][text2.length()+1];
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        int max = 0;
        for(int i=1;i<=text1.length();i++){
            for(int j=1;j<text2.length();j++){
                if(c1[i-1]==c2[j-1]){
                    for(int x=1;x<i;x++){
                        for(int y=1;y<j;y++){
                            dp[i][j] = Math.max(dp[x][y]+1,dp[i][j]);
                        }
                    }
                }
                max = max>dp[i][j]?max:dp[i][j];
                
            }
        }
        return max;*/
        //卡哥做法:dp[i][j]代表0~i-1 0~j-1最长公共子序列的长度
        //确定递推公式
        //从dp的定义处罚,相当于两者都往前走一步的最大值+1
        // 若text1[i] = text2[j]  dp[i][j] = dp[i-1][j-1]+1
        // 若不相等 则dp[i][j] 要获取之前两者最长公共子序列的最大值 
        //dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
        //dp数组初始化
        //都为0
        //确定遍历顺序
        //从前往后
        //举例推导dp数组
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        for(int i=1;i<=text1.length();i++){
            //少打了个=,要去debug
            for(int j=1;j<=text2.length();j++){
                if(c1[i-1]==c2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                if(c1[i-1]!=c2[j-1]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

1035.不相交的线

力扣题目链接(opens new window)

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在,我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。

以这种方法绘制线条,并返回我们可以绘制的最大连线数。

动态规划Day14(子序列第二天),动态规划,算法

看到题目的第一想法
               

        和上一道题一样的思路,直接写,通过了

        

看到代码随想录之后的想法

        用动态规划

        确定dp数组和每个下标的含义

        dp[i][j]记录末尾为i-1和j-1的最长的子序列的长度

        

        确定递推公式

        要从递推公式来进行考虑

       若text1[i] = text2[j] 则在之前的基础上+1

                dp[i][j] = dp[i-1][j-1]+1; 

        若text1[i] != text2[j] 则等于之前的最大值 

                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

         dp数组初始化

                  因为dp[i][j] 代表0~i-1,0~j-1的最大子序列,则不需要定义dp[i][0],dp[0][j],因为0 代表-1没有意义

        确定遍历顺序

        从前往后,从上往下

        举例推导dp数组           

        打印dp数组

        打印最后一个元素

自己实现过程中遇到的困难

       自己需要注意i-1和j-1这个点,同时for循环的条件需要 i<=  j<=  不要忘了等号

        要结合dp的定义来写递推公式

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //二维数组?dp[i][j]记录text1下标i到text2下标j的长度
        //上一题是连续,这一题不连续
        //dp[i][j]后遍历 若 text1[i] = text2[j]
        //则遍历到i,j,不断更新dpij的最大值
        //text1 text2
        /*int[][] dp = new int[text1.length()+1][text2.length()+1];
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        int max = 0;
        for(int i=1;i<=text1.length();i++){
            for(int j=1;j<text2.length();j++){
                if(c1[i-1]==c2[j-1]){
                    for(int x=1;x<i;x++){
                        for(int y=1;y<j;y++){
                            dp[i][j] = Math.max(dp[x][y]+1,dp[i][j]);
                        }
                    }
                }
                max = max>dp[i][j]?max:dp[i][j];
                
            }
        }
        return max;*/
        //卡哥做法:dp[i][j]代表0~i-1 0~j-1最长公共子序列的长度
        //确定递推公式
        //从dp的定义处罚,相当于两者都往前走一步的最大值+1
        // 若text1[i] = text2[j]  dp[i][j] = dp[i-1][j-1]+1
        // 若不相等 则dp[i][j] 要获取之前两者最长公共子序列的最大值 
        //dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
        //dp数组初始化
        //都为0
        //确定遍历顺序
        //从前往后
        //举例推导dp数组
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        for(int i=1;i<=text1.length();i++){
            //少打了个=,要去debug
            for(int j=1;j<=text2.length();j++){
                if(c1[i-1]==c2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                if(c1[i-1]!=c2[j-1]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

53. 最大子序和

力扣题目链接(opens new window)

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

  • 输入: [-2,1,-3,4,-1,2,1,-5,4]
  • 输出: 6
  • 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
看到题目的第一想法
               

        之前用贪心写过,贪心的思路是找非负的sum,然后开始累加

        dp 的思路

        dp[i]以i为终点的最大和

        递推公式:dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

        初始化:dp[0] = nums[0]

        打印:整个dp中的最大值

看到代码随想录之后的想法

        用动态规划,和我的思路一样

自己实现过程中遇到的困难

        注意下边界条件

       比较顺利,不过贪心的时候需要注意sum的调整文章来源地址https://www.toymoban.com/news/detail-820526.html

class Solution {
    public int maxSubArray(int[] nums) {
        /*//动态规划
        //确定dp数组和下标的含义
        //到达当前下标的最大和
        //确定递推公式
        //dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
        //dp数组初始化
        //dp[0]=nums[0]
        //举例dp数组
        if(nums.length==1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            max=max>dp[i]?max:dp[i];
        }
        return max;*/
    //贪心从非负的开始找,若sum<0 则继续往下找第一个非负的
        int result = Integer.MIN_VALUE;
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            if(sum>result){
                result=sum;
            }
            if(sum<0){
                sum=0;
            }
            

        }
        return result;

    }
}

到了这里,关于动态规划Day14(子序列第二天)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(50)
  • 算法 DAY52 动态规划10 1143.最长公共子序列 1035.不相交的线 53. 最大子数组和

    本题和动态规划:718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了 1、dp数组 dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j] 2、递推公式 因为不强调是连续的,当前dp[i][j] 就有三种路径可以选:dp[i-1][j] dp[i][j-1]

    2024年02月03日
    浏览(65)
  • Day46- 动态规划part14

    题目一:1143. 最长公共子序列 1143. 最长公共子序列 给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。 一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的

    2024年02月21日
    浏览(40)
  • 研习代码 day46 | 动态规划——子序列问题2

            1.1 题目         给定两个字符串  text1  和  text2 ,返回这两个字符串的最长  公共子序列  的长度。如果不存在  公共子序列  ,返回  0  。         一个字符串的  子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下

    2024年02月04日
    浏览(37)
  • 研习代码 day47 | 动态规划——子序列问题3

            1.1 题目         给定字符串  s  和  t  ,判断  s  是否为  t  的子序列。         字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如, \\\"ace\\\" 是 \\\"abcde\\\" 的一个子序列,而 \\\"aec\\\" 不是)。

    2024年02月04日
    浏览(44)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • 算法笔记14.动态规划

    就是切割问题变成一堆小问题,最好子问题之间可以递推,这样就能利用之前的子问题的答案得出新的结果。 可以削减总量,比如求n个数的什么什么,可以削n的大小,n削到n-1……一直到1,1的结果很好求,然后利用1的结果求2,然后再一直求到n。 也可以不削总量削单量,比

    2024年04月15日
    浏览(28)
  • 算法:动态规划——最长公共子序列

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。若用分治法解这类问题,则分解得到的

    2023年04月27日
    浏览(60)
  • 【算法-动态规划】最长公共子序列

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年01月23日
    浏览(47)
  • 动态规划算法 | 最长递增子序列

    通过查阅相关资料 发现动态规划问题一般就是求解最值问题 。这种方法在解决一些问题时应用比较多,比如求最长递增子序列等。 有部分人认为动态规划的核心就是:穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。 首先,笔者认为动态规划中

    2024年02月06日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包