D45&&D46|动态规划之子序列问题

2024-01-01 12:30:20

300.最长递增子序列:

初始思路:

动态规划五部曲:

1)dp数组的定义,dp[i]表述数组第i个元素大于前面几个值;

2)dp数组的迭代,min = nums[x]表示递增数组中的最后一个值,如果nums[i]>min;nums[i]=nums[i-1]+1;else nums[i] = nums[i-1]

3)初始化 dp[0] = 1

4)顺序:前序;

5)遍历:有点不对,5和3那里有点不对劲,先试试。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0]=1;
        int minvalue = nums[0];
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>minvalue){
                dp[i] = dp[i-1]+1;
                minvalue = nums[i];
            }else{
                dp[i] = dp[i-1];
                minvalue = nums[i];
            }
        }
        return dp[nums.length-1];
    }
}

无法正确通过,所以题解不正确。

题解复盘:

动态规划五部曲 :

1)dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2)if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3)每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.

4)从前向后遍历

5)

这道题看实例推导要比看文字更简单些,一个循环遍历数组中所有元素,一个循环遍历数组中在i之前的元素,?dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度,

就上面的例子比较好理解当i遍历到3时,j会从0开始遍历到2;3>0 dp[3]=dp[0]+1=2;3>1 dp[3] = dp[1]+1 = 3,3>0,dp[3] = max(dp[3],dp[2]+1) = 3;

result记录遍历中的最大值


674.最长连续递增序列

初始思路:

这道题相对于上一道题新增了连续的条件,感觉反而简单了,如果当前元素大于前一元素,dp[i]++,如果小于的话dp[i]归一.

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length<=1){return nums.length;}
        int[] dp = new int[nums.length];
        int result = 0;
        for(int i = 0;i<nums.length;i++){
            dp[i] = 1;
        }
        for(int i = 1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                dp[i] = dp[i-1]+1;
            }else{
                dp[i] = 1;
            }
            result = Math.max(dp[i],result);
        }
        return result;
    }
}

题解复盘:

关键在于递推公式的变化 :

  1. 确定递推公式

如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。

即:dp[i] = dp[i - 1] + 1;

注意这里就体现出和动态规划:300.最长递增子序列?(opens new window)的区别!

因为本题要求连续递增子序列,所以就只要比较nums[i]与nums[i - 1],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)

既然不用j了,那么也不用两层for循环,本题一层for循环就行,比较nums[i] 和 nums[i - 1]。

这里大家要好好体会一下!


718.最长重复子数组?

初始思路&&题解复盘:

感觉对照示例会更容易理解这部分的解题思路:

1)确定dp数组及其下标的含义:dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。?

2)递推公式:即当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;

此处注意A[i - 1] 和B[j - 1]相等即推导dp[i][j]

3)初始化:为0即可

4)遍历顺序:一层循环遍历一个数组

5)举例:如下。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        int result = 0;
        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]);
                
            }
            
        }
        return result;
    }
}

1143.最长公共子序列

?初始思路:

相对于上面一道题,两个字符串的长度不太一样了,而且数字也不是连续的。所以循环顺序一定要有所调整。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int result = 0;
        char[] t1 = text1.toCharArray();
        char[] t2 = text2.toCharArray();

        int[][] dp = new int[t1.length+1][t2.length+1];
        for(int i = 1;i<t1.length+1;i++){
            for(int j = 1;j<t2.length+1;j++){
                if(t1[i-1]==t2[j-1]){
                    //System.out.println(t1[i-1]);

                    dp[i][j] = dp[i-1][j-1]+1;
                    
                    //System.out.println(dp[i][j]);
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
                result = Math.max(result,dp[i][j]);
            }
        }
        return result;
    }
}

?以上是标答:

我的答案无法全部AC的递归逻辑是

                if(t1[i-1]==t2[j-1]){
                    //System.out.println(t1[i-1]);

                    dp[i][j] =  Math.max(dp[i-1][j],dp[i][j-1])+1;
                    
                    //System.out.println(dp[i][j]);
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }

区别在哪呢?

?

不分析我的错误逻辑了,

可以看到如果text1和text2中的c相等,此时结果就等于ab串和a串中重复的最大子数组和+1;

如果text1和text2中的b和c不等,此时结果就是a串和ac串或ab串和a串中重复的最大子数组和。?


1035.不相交的线

初始思路:

同上一题相同,按照顺序但不连续的重复子数组

718是一定是要连续的重复子数组。


53.最大子数组和

初始思路:

如何转换成dp问题?

确定递推公式

dp[i]只有两个方向可以推出来:

  • dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
  • nums[i],即:从头开始计算当前连续子序列和

一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length==1){return nums[0];}
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = nums[0];
        for(int i = 1;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            result = Math.max(dp[i],result);
        }
        return result;
    }
}

文章来源:https://blog.csdn.net/Q77ian/article/details/135303443
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。