首页 > 编程语言 >代码随想录算法训练营第43天:动态规划part10:子序列问题

代码随想录算法训练营第43天:动态规划part10:子序列问题

时间:2024-08-15 11:53:28浏览次数:16  
标签:nums int max part10 随想录 43 序列 递增 dp

300.最长递增子序列

力扣题目链接(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]
  • 输出:4
  • 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

子序列问题分析:

dp[i]的定义

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

为什么一定表示 “以nums[i]结尾的最长递增子序” ,因为我们在 做 递增比较的时候,如果比较 nums[j] 和 nums[i] 的大小,那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾, 要不然这个比较就没有意义了,不是尾部元素的比较那么 如何算递增呢。

状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

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

注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值。

dp[i]的初始化

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

确定遍历顺序

dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1,那么是从前到后,还是从后到前遍历都无所谓,只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

注意**:概括来说:不连续递增子序列的跟前0-i 个状态有关,连续递增的子序列只跟前一个状态有关——这也是考虑如何构建动态规划算法的方法

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)
int lengthOfLIS(int* nums, int numsSize) {
   int dp[numsSize];
   dp[0]=1;
   int max_ans=1;//结果不一定在最后一个位置

   for (int i=1;i<numsSize;i++){
        dp[i]=1;//为什么要初始化成1:包含自己必然是最大的子序列,尤其是涉及到fmax,不能随便初始化的
        for (int j=0;j<i;j++){
            if(nums[j]<nums[i]) dp[i]=fmax(dp[i],dp[j]+1);
        }
        printf("%d",dp[i]);
        max_ans=fmax(max_ans, dp[i]);
    }
    return max_ans;
}

674. 最长连续递增序列

力扣题目链接(opens new window)

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1:

  • 输入:nums = [1,3,5,4,7]
  • 输出:3
  • 解释:最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。

示例 2:

  • 输入:nums = [2,2,2,2,2]
  • 输出:1
  • 解释:最长连续递增序列是 [2], 长度为1。

可以不用动态规划直接做:贪心 o(n) o(1)复杂度

int findLengthOfLCIS(int* nums, int numsSize) {
    int max_ans=1;
    int this=1;
    for (int i=1;i<numsSize;i++){
        if(nums[i]>nums[i-1]) {
            this++;
            max_ans=fmax(this, max_ans);
        }        
        else {
            this=1;
        }
    }
    return max_ans;
}

感觉动规做法过于复杂:

int findLengthOfLCIS(int* nums, int numsSize) {
    int max_ans=1;
    int dp[numsSize];
    
    dp[0]=1;
    for (int i=1;i<numsSize;i++){
        dp[i]=1;
        if(nums[i]>nums[i-1])  dp[i]=dp[i-1]+1;
     
        max_ans=fmax(max_ans, dp[i]);
    }
    return max_ans;
}

718. 最长重复子数组

力扣题目链接(opens new window)

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例:

输入:

  • A: [1,2,3,2,1]
  • B: [3,2,1,4,7]
  • 输出:3
  • 解释:长度最长的公共子数组是 [3, 2, 1] 。

提示:

  • 1 <= len(A), len(B) <= 1000
  • 0 <= A[i], B[i] < 100

分析:

dp【i】【j】:是以i位置、j位置为结尾的匹配的情况——所以只和左上位置元素相关

之前考虑的时候,考虑成i位置、j位置以前的匹配的最大值情况,发现没有办法从上一个状态推导到这个状态——优先直接出结果,如果不能出结果,可以退而求其次,最大值的任务落在max_ans

上,优先考虑本次状态的情况

int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int dp[nums1Size][nums2Size];
    memset(dp,0, sizeof(dp));
    if(nums1[0]==nums2[0]) dp[0][0]=1;
    int max_ans=0;

    for (int i=1;i<nums1Size;i++){
        if(nums2[0]==nums1[i]) dp[i][0]=1;
        max_ans=fmax(max_ans, dp[i][0]);
    }

    for (int j=1;j<nums2Size;j++){
        if(nums1[0]==nums2[j]) dp[0][j]=1;
        max_ans=fmax(max_ans, dp[0][j]);
        
    }

    for (int i=1;i<nums1Size;i++){
        for (int j=1;j<nums2Size;j++){
            if(nums1[i]==nums2[j]) dp[i][j]=dp[i-1][j-1]+1;
            max_ans=fmax(max_ans, dp[i][j]);
        }
    }


    return max_ans;
    
}

标签:nums,int,max,part10,随想录,43,序列,递增,dp
From: https://blog.csdn.net/weixin_65180740/article/details/141183427

相关文章

  • 代码随想录day30 || 452 引爆气球,435 无重叠区间,763 划分字母区间
    452射爆气球funcfindMinArrowShots(points[][]int)int{ //思路,尝试按照startasc,endasc排序一下,取交集射爆 iflen(points)==1{ return1 } sort.Slice(points,func(i,jint)bool{ ifpoints[i][0]==points[j][0]{ returnpoints[i][1]<points......
  • 520-基于ZU15EG 适配AWR2243的雷达验证底板 XCZU15EG架构高速信号处理板
    基于ZU15EG适配AWR2243的雷达验证底板一、板卡概述   本板卡系北京太速科技自主研发,基于MPSOC系列SOC XCZU15EG-FFVB1156架构,搭载两组64-bit DDR4,每组容量32Gb,最高可稳定运行在2400MT/s。另有1路10G SFP+光纤接口、1路40G QSFP光纤接口、1路USB3.0接口、1路千兆网络接口......
  • 代码随想录Day15
    110.平衡二叉树(优先掌握递归)给定一个二叉树,判断它是否是平衡二叉树平衡二叉树是指该树所有节点的左右子树的深度相差不超过1。示例1:输入:root=[3,9,20,null,null,15,7]输出:true示例2:输入:root=[1,2,2,3,3,null,null,4,4]输出:false示例3:输入:root=[]输出:t......
  • D43 2-SAT+前缀优化 P6378 [PA2010] Riddle
    视频链接: P6378[PA2010]Riddle-洛谷|计算机科学教育新生态(luogu.com.cn)//2-SAT+前缀优化O(n+m)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#definex0(x)x//点#definex1(x)x+n//反点#definep0(x)x+2*n......
  • 【代码随想录】一、数组:3.双指针 - 977.有序数组的平方
    本文为977.有序数组的平方的解法,部分图文参考自代码随想录977.有序数组的平方。1.题目1:977.有序数组的平方1.1.解法1:直接排序classSolution{public:vector<int>sortedSquares(vector<int>&nums){for(inti=0;i<nums.size();i++){n......
  • 【代码随想录】一、数组:2.移除元素
    部分图文参考于:代码随想录-移除元素和力扣官方解法。1.题目1★:27.移除元素1.1.解法1:暴力解法考验对数组底层实现的理解:数组的元素是不能删的,只能覆盖。通过两层for循环来求解,外层for循环遍历数组元素,内层for循环将目标值进行覆盖。classSolution{public:intremove......
  • 【代码随想录】一、数组:1.二分查找
    部分图文参考于:代码随想录-二分查找,本文仅作为个人学习使用,如有侵权,请联系删除。1.概念二分查找也称折半查找(BinarySearch),是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知,运用二分搜索的前提是数组必须是有序的,这里需要注意的是,我们的输入不一定是数组,也......
  • 【代码随想录】一、数组:理论基础
    原文链接:代码随想录-数组理论基础,本文仅作为个人学习使用,如有侵权,请联系删除。数组是非常基础的数据结构,在面试中,考察数组的题目一般在思维上都不难,主要是考察对代码的掌控能力。数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下......
  • 代码随想录训练营day20|235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插入操作,450
    二叉搜索树的最近公共祖先题目根据二叉搜索树的特性,它的公共祖先肯定是值夹在p和q之间的(满足此条件的第一个点)TreeNode*getroot(TreeNode*root,TreeNode*p,TreeNode*q){ if(rooot==NULL)returnNULL; if(root->val<p->val&&root->val<q->val){ returngetroot(r......
  • 代码随想录day29 || 134 加油站,135 分糖果,860 柠檬水找零,406 根据身高重建队列
    加油站funccanCompleteCircuit(gas[]int,cost[]int)int{ //思路,首先统计一个差值数组,表示行驶到下一个加油站可以补充的油量,然后加总差值数组, //如果小于0,表示从起始位置到目前为止剩余油量小于0,不足以跑完全程,同时将起始位置放到遍历的下一个位置 iflen(gas)==0......