首页 > 其他分享 >day52

day52

时间:2023-03-07 21:12:51浏览次数:33  
标签:遍历 nums int res 递增 day52 dp

1、leetcode300 最长递增子序列

  1. 动规五部曲

    1. dp[i] : 以nums[i]结尾的数组的递增子序列的最大长度

      做递增比较的时候,如果比较 nums[j] 和 nums[i] 的大小,那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾, 否则这个比较就没有意义了

    2. 递推公式

      if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
      注意:这里不是要dp[i] 与 dp[j] + 1进行比较,而是要取dp[j] + 1的最大值。
      
    3. 初始化

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

    4. 遍历顺序

      1. dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。
      2. j其实就是遍历0到i-1,那么是从前到后,还是从后到前遍历都无所谓,只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。
      3. 遍历i的循环在外层,遍历j则在内层
    5. 举例

  2. 代码

    class Solution {
        public int lengthOfLIS(int[] nums) {
            if(nums.length <= 1) return nums.length;
    
            int[] dp = new int[nums.length];
            Arrays.fill(dp, 1);
            int res = 1;
    
            for(int i=1; i<nums.length; i++) {
                for(int j=0; j<i; j++) {
                    if(nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                if(dp[i] > res) res = dp[i];// 取长的子序列
            }
    
            return res;
    
        }
    }
    

2、leetcode最长连续递增序列

  1. 动规五部曲

    1. dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]

      • 以下标i为结尾,并不是说一定以下标0为起始位置。
    2. 递推公式 【与上一题的区别,因为该题要求 连续递增

      if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
      
    3. 初始化

      以下标i为结尾的连续递增的子序列长度最少也应该是1,即就是nums[i]这一个元素

    4. 遍历顺序

      • 从前往后遍历
    5. 举例

  2. 动规代码

    class Solution {
        public int findLengthOfLCIS(int[] nums) {
            if(nums.length <= 1) return nums.length;
    
            int[] dp = new int[nums.length];
            Arrays.fill(dp, 1);
            int res = 0;
    
            for(int i=1; i<nums.length; i++) {
                if(nums[i] > nums[i-1]) {
                    dp[i] = dp[i-1] + 1; // 连续记录
                } 
                
                if(dp[i] > res) res = dp[i];
            }
    
            return res;
    
        }
    }
    
  3. 贪心代码

    class Solution {
        public int findLengthOfLCIS(int[] nums) {
            if(nums.length <= 1) return nums.length;
            
            int count = 1;
            int res = 1;// 连续子序列最少也是1
    
            for(int i=1; i<nums.length; i++) {
                if(nums[i] > nums[i-1]) { // 连续记录
                    count++;
                } else { // 不连续,count从头开始
                    count = 1;
                }
                res = Math.max(res, count);
            }
    
            return res;
    
        }
    }
    

3、leetcode718 最长重复子数组

  1. 动规五部曲

    1. dp[i] [j] : 以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i] [j]。
      • 定义决定:在遍历dp[i] [j]的时候i 和 j 都要从1开始
    2. 递推公式
      • 当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1] [j - 1] + 1;
    3. 初始化
      • 根据dp[i] [j]的定义,dp[i] [0] 和dp[0] [j]其实都是没有意义的!但dp[i] [0] 和dp[0] [j]要初始值,因为 为了方便递归公式dp[i] [j] = dp[i - 1] [j - 1] + 1;
      • 所以dp[i] [0] 和dp[0] [j]初始化为0。
    4. 遍历顺序
      • 外层for循环遍历A,内层for循环遍历B。 or 外层for循环遍历B,内层for循环遍历A。
      • 从前向后遍历
      • i,j 从1开始
      • 题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp[i] [j]的最大值记录下来。
    5. 举例
  2. 代码

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

标签:遍历,nums,int,res,递增,day52,dp
From: https://www.cnblogs.com/hzj-bolg/p/17189664.html

相关文章

  • 【算法训练营day52】LeetCode300. 最长递增子序列 LeetCode674. 最长连续递增子序列 L
    LeetCode300.最长递增子序列题目链接:300.最长递增子序列独上高楼,望尽天涯路感觉和之前的动态规划思路还不一样,没有想出好的递推公式。慕然回首,灯火阑珊处解决这道题......
  • day52- 数据库的列类型与字段属性
    数据库的列类型数值tinyint十分小的数据一字节smallint较小的数据二字节int标准的整数四字节bigint较大的数据八字节float浮点数四字节dou......
  • 前端Vue2-Day52
    Vue组件化编程:非单文件组件:一个文件包含n个组件①定义组件:Vue.extend(options)创建,在options内部不能写el(组件都需要经过vm统一管理和分配),data必须写成函数模式,避免组......
  • 学习python-Day52
    今日学习内容作业讲解用户管理系统(单表)配置文件settings中关于template的文件路径修改和添加。将新建的应用注册接口前缀模型类在models文件中创建各个类对......
  • python学习Day52
    Day52今日内容概要CSS属性盒子模型浮动布局overflow溢出属性定位属性z-index层叠顺序opacity透明效果手搭页面练习JavaScript简介JS变量与常量JS数据类......