动态规划:子序列问题(C++)

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

前言

动态规划往期文章:

  1. 动态规划入门:斐波那契数列模型以及多状态
  2. 动态规划:路径和子数组问题

子序列问题

1.最长递增子序列(中等)

链接:最长递增子序列

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    对于线性dp,我们通常采用下面两种表示:
    (1)以某个位置为结尾,……
    (2)以某个位置为起点,……
    这两种方式我们通常采用第一种,以某个位置为结尾,再结合题目要求,我们可以定义状态表示为dp[i]:以i位置为结尾的所有子序列中,最长递增子序列的长度。

  2. 状态转移方程
    对于以i位置为结尾的子序列,一共有两种可能:
    (1)不接在别人后面,就自己一个,dp[i] = 1
    (2)接在[0,1,2,……,i - 1]这些位置后面,设0 <= j <= i - 1,能保持子序列递增(nums[j] < nums[i])就可以接在该位置后面。
    从0~i - 1枚举j,看接在那个位置后面长度最大:
    即dp[i] = max(dp[i], dp[j] + 1)

  3. 初始化
    每个位置最小都为1,全都初始化为1。

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序为从左往右

  5. 返回值
    没法直接确定最长子序列的结尾位置,一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        //dp[i]表示以i位置为结尾的最长递增子序列
        vector<int> dp(n, 1);    
       int ret = 1;
        for(int i = 1; i < n; i++)
        {
            //从[0, i-1]看一圈,找接在那个符合条件的位置后面可以让子序列最长
            for(int j = 0; j < i; j++)       
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);                         
            //看看能不能更新最大
            ret = max(ret, dp[i]);
        }
        return ret;
        //时间复杂度:O(N ^ 2)
        //空间复杂度:O(N)
    }
};

2.摆动序列(中等)

链接:摆动序列

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    依据前面的经验,我们依据可以定义状态表示为dp[i]:以i位置为结尾的所有摆动序列中的最大长度

  2. 状态转移方程
    对于长度大于1的摆动序列,其有两种情况:
    (1)处于上升状态,比如(1, 7, 4, 9)。
    (2)处于下降状态,比如(1, 17, 10)。
    因此我们需要同时记录两种状态,其中f[i]表示以i位置为结尾并处于上升状态的最长摆动序列长度,g[i]表示处于下降状态

    摆动序列分析完了,我们再来分析单个位置,一共有两种可能:
    (1)不接在别人后面,自己玩,dp[i] = 1
    (2)接在[0,1,2,……,i - 1]这些位置后面,设0 <= j <= i - 1。
    ①如果接在j位置后处于上升状态(nums[i] - nums[j] > 0),需要以j位置为结尾并处于下降状态的状态,即f[i] = g[j] + 1
    ②如果接在j位置后处于下降状态(nums[i] - nums[j] < 0),需要以j位置为结尾并处于上升状态的状态,即g[i] = f[j] + 1

  3. 初始化
    序列长度最小为1,所有位置全都初始化为1

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序为从左往右

  5. 返回值
    没法直接确定最长摆动序列的结尾,所以一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        //dp[i]表示以i位置为结尾的最长摆动序列长度
        int n = nums.size();
        vector<int> f(n, 1);//处于上升状态
        vector<int> g(n, 1); //处于下降状态
        int ret = f[0]; //记录最终结果
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                int gap = nums[i] - nums[j];
                //处于上升
                if(gap > 0)
                    f[i] = max(f[i], g[j] + 1);
                //处于下降
                else if(gap < 0)
                    g[i] = max(g[i], f[j] + 1);
                //相同的情况为1不用处理
            }
            ret = max({ret, f[i], g[i]});
        }
        return ret;
        //时间复杂度:O(N ^ 2)
        //空间复杂度:O(N)
    }
};

3.最长递增子序列的个数(中等)

链接:最长递增子序列的个数

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    依据前面的经验,我们可以定义状态表示dp[i]:以i位置为结尾的最长递增子序列个数

  2. 状态转移方程
    要更新当前位置的最长递增子序列个数,无非是看接在那几个位置后面长度最大,但问题就在于现在只有前面位置的序列个数,没有长度,所以我们需要再加一个表来记录长度:
    (1)count[i]:以i位置为结尾的最长递增子序列个数
    (2)len[i]:以i位置为结尾的最长递增子序列长度

    len[i]前面已经讲过,我们分析count[i]:
    (1)不接在别人后面,最大长度就为1,count[i] = 1
    (2)接在[0,1,2,……,i - 1]这些位置后面,设0 <= j <= i - 1,能保持子序列递增(nums[j] < nums[i])就可以接在该位置后面。

    从0~i - 1枚举j,依据接在那个位置后面的长度进行分析:
    ①比原来长度小(len[i] > len[j] + 1),不用管。
    ②比原来长度大(len[i] < len[j] + 1),原来的序列个数无论多少都必须狠狠切割了,个数更新为更长的,即count[i] = count[j]
    ③和原来长度一样(len[i] == len[j] + 1),计数增加,即count[i] += count[j]

  3. 初始化
    序列长度最小为1,全都初始化为1

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序为从左往右

  5. 返回值
    (1)完成了前面的工作,我们知道以每一个位置为结尾的最长递增子序列长度和个数,但是并不知道以那几个位置为结尾的序列最长,所以我们需要一边dp一边更新最大长度max_length
    (2)知道了最大长度,我们只需要遍历一次count表,把长度为max_length的序列统计出来即可

  • 代码实现
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> count(n, 1); //f[i]表示以i位置为结尾的最长子序列个数
        auto len = count; //g[i]表示以i位置为结尾的最长递增子序列长度
        int max_length = len[0];
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    //找到了更加长的
                    if(len[i] < len[j] + 1)
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                    else if(len[i] == len[j] + 1) //长度相同                 
                        count[i] += count[j];               
                }
            }
            max_length = max(max_length, len[i]);
        }
        int ret = 0;    //返回值
        //遍历一次,计算最长序列个数
        for(int i = 0; i < n; i++)      
            if(len[i] == max_length)
                ret += count[i];
        return ret;
        //时间复杂度:O(N ^ 2)
        //空间复杂度:O(N)
    }
};

4.最长数对链(中等)

链接:最长数对链

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    依据前面经验,我们定义状态表示dp[i]:以i位置为结尾最长数对链长度

  2. 状态转移方程
    这个题目的分析其实和前面的最长递增子序列基本一致。
    (1)不接在别人后面,自己玩,dp[i] = 1
    (2)接在[0,1,2,……,i - 1]这些位置后面,设0 <= j <= i - 1,满足数对链要求(pairs[j][1] < pairs[i][0])就可以接在该位置后面。
    从0~i - 1枚举j,看接在那个位置后面长度最大:
    即dp[i] = max(dp[i], dp[j] + 1)

  3. 初始化
    长度最小为1,全都初始化为1

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序为从左往右

  5. 返回值
    没法直接确定最长数对链的结尾,所以一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {              
        sort(pairs.begin(), pairs.end());   //先排序
        int n = pairs.size();
        //dp[i]表示以i位置为终点的最长长度
        vector<int> dp(n, 1);
        int ret = 1; //记录最长
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)                      
                if(pairs[j][1] < pairs[i][0]) //如果可以接在后面            
                    dp[i] = max(dp[i], dp[j] + 1);                         
            ret = max(ret, dp[i]);
        }
        return ret;
        //时间复杂度:O(N ^ 2)
        //空间复杂度:O(N)
    }
};

5.最长定差子序列(中等)

链接:最长定差子序列

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    依据前面的经验,我们定义状态表示dp[i]:以下标i位置为结尾的最长等差子序列长度

  2. 状态转移方程
    这个题目最好想的做法就是递增子序列的做法,但这样写会超时,我们可以分析一下原因:
    (1)递增子序列可以接在很多位置的后面。
    (2)等差子序列只能接在固定的位置后面,比如(1, 2, 3, 4),difference为1,里面的4只能接在3后面,其它的判断都是多余的。

    那我们就换一种思路,还是(1, 2, 3, 4),difference为1这个例子,我们在填4位置的时候,如果能够直接找到以3(arr[i] - difference)为结尾的最长递增子序列就好了。
    我们可以把元素arr[i]与dp[i]绑定,创建一个哈希表hash,我们可以直接在这个哈希表中做动态规划,那状态转移方程就为:
    hash[i] = hash[arr[i] - difference] + 1

  3. 初始化
    在填表的时候,如果前置状态不存在,我们不单独处理(0加1变成1刚好对应自己一个的情况)。因此我们只需要把第⼀个元素放进哈希表中, hash[arr[0]] = 1即可

  4. 填表顺序
    保证填当前状态时,所需状态已经计算过,填表顺序为从左往右

  5. 返回值
    不确定最长等差子序列的结尾,所以一边dp一边更新最大值

  • 代码实现
class Solution
{
    public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        // 创建⼀个哈希表
        unordered_map<int, int> hash; // {arr[i], dp[i]}
        hash[arr[0]] = 1; // 初始化
        int ret = 1;
        for(int i = 1; i < arr.size(); i++)
        {
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret, hash[arr[i]]);
        }
        return ret;
        //时间复杂度:O(N)
        //空间复杂度:O(N)
    }
};

6.最长的斐波那契子序列的长度(中等)

链接:最长的斐波那契子序列的长度

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    依据经验我们可能会定义状态表示为以i位置为结尾的最长斐波那契序列的长度,但这样定义有一个致命的问题:不知道接在某一个位置后能否构成斐波那契序列
    一个元素无法确定,但如果我们知道斐波那契序列的后两个元素,我们就可以推导出前一个元素,从而解决前面的问题。
    所以定义一个二维表dp[i][j]:以i,j位置为后两个元素的最长斐波那契序列的长度

  2. 状态转移方程
    规定 i 比 j 小,其中j从[2, n - 1]开始枚举,i从[1, j - 1]开始枚举。
    设 nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = c - b ,我们根据 a 的情况讨论:
    (1)a存在,设其下标为k,并且 a < b,这个时候c可以接在以a、b为结尾的斐波那契序列后面,则dp[i][j] = dp[k][i] + 1
    (2)a存在,但是 b < a < c,这个时候只能b和c两个自己构成,dp[i][j] = 2
    (3)a不存在,这个时候只能b和c两个自己构成,dp[i][j] = 2

    我们发现,在状态转移⽅程中,我们需要确定 a 元素的下标。因此我们可以在 dp 之前,将所有的「元素 + 下标」绑定在⼀起,放到哈希表中。

  3. 初始化
    长度最小为2,全都初始化为2

  4. 填表顺序
    固定最后一个数,枚举倒数第二个数

  5. 返回值
    不确定最长斐波那契子序列的结尾,所以一边dp一边更新最大值

  • 代码实现
class Solution {
public:   
    int lenLongestFibSubseq(vector<int>& arr)
    {
        int n = arr.size();
        //i->j
        dp[i][j]表示以i,j为后两个的斐波那契数列最长长度
        vector<vector<int>> dp(n, vector<int>(n, 2));
        unordered_map<int, int> hash;
        for(int i = 0; i < n; i++) hash[arr[i]] = i;

        int ret = 2;
        for (int j = 2; j < n; j++)
        {
            for (int i = 1; i < j; i++)
            {
                int former = arr[j] - arr[i];
                //a b c,a < b 并且a存在
                if (former < arr[i] &&  hash.count(former))
                {
                    dp[i][j] = dp[hash[former]][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
        }
        //斐波那契序列最小为3,为2的情况返回0
        return ret > 2 ? ret : 0;
        //时间复杂度:O(N)
        //空间复杂度:O(N ^ 2)
    }
};

7.最长等差序列(中等)

链接:最长等差序列

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    和前面一道题类似,只有一个元素无法确定等差序列的样子,我们需要有后面两个元素才能确定,故定义一个二维表dp[i][j]:以i,j为后两个元素的最长等差子序列的长度

  2. 状态转移方程
    规定 i 比 j 小,设 nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = 2 * nums[i] - nums[j] (等差序列的性质捏) ,我们根据 a 的情况讨论:
    (1)a存在,设其下标为k,这个时候c可以接在以a、b为结尾的序列后面,则dp[i][j] = dp[k][i] + 1
    (2)a不存在,这个时候只能b和c两个自己构成,dp[i][j] = 2

    我们发现,在状态转移方程中,我们需要确定 a 元素的下标。因此我们可以将所有的「元素 + 下标」绑定在⼀起,放到哈希表中。对于这个题目哈希表有两种方案:
    (1)在dp前就直接放入哈希表,可能出现重复的元素(这个题目是乱序的,前面一题严格递增),要记录这些重复元素,需要让它们的下标形成一个数组,填表前要先遍历数组找到需要的下标,时间消耗很大,这个方案通过不了
    (2)只能采取一边dp一边存入哈希表的方式,在i位置使用完后存入哈希表中,但填表顺序必须固定倒数第二,枚举倒数第一,不能采用上一题固定倒一,枚举倒二的填表方式。我们看这个例子:【0,2,4,4,4,6,8,4,9,4,4】,最后一个4固定,第一个4为倒数第二时,应该去找之前4的下标(这里前面是[0,2],没有4,意味着这个数不应该在哈希表中,但固定倒一,枚举倒二的填表方式使得哈希表中是有保存的,这个时候就完全乱了)

  3. 初始化
    长度最小为2,全部初始化为2

  4. 填表顺序
    填表顺序为固定倒数第二,枚举倒数第一

  5. 返回值
    不确定最长等差序列的结尾,所以一边dp一边更新最大值

  • 代码实现
class Solution {
public:
    //dp[i][j]表示以i,j为结尾的最长等差数列长度
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash;       
        hash[nums[0]] = 0;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        for (int i = 1; i < n; i++) //倒数第二个
        {
            for (int j = i + 1; j < n; j++)
            {
                int former = 2 * nums[i] - nums[j];
                if (hash.count(former))
                    dp[i][j] = dp[hash[former]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i;
        }
        return ret;
        //时间复杂度:O(N ^ 2)
        //空间复杂度:O(N ^ 2)
    }
};

8.等差数列划分II - 子序列(困难)

链接:等差数列划分II - 子序列

  • 题目描述
    动态规划:子序列问题(C++),算法,动态规划,c++,算法,笔记,力扣

  • 做题步骤

  1. 状态表示
    和前面一道题一致,只有一个元素无法确定等差序列的样子,我们需要有后面两个元素才能确定,故定义一个二维表dp[i][j]:以i,j为后两个元素的等差子序列个数

  2. 状态转移方程
    首先,这个题目不存在重复的等差子序列,只要组成的元素位置不同就视为不同子序列,比如[7,7,7,7,7]这个数组等差子序列个数高达16个。

    规定 i 比 j 小,设 nums[i] = b, nums[j] = c ,那么这个序列的前⼀个元素就是 a = 2 * nums[i] - nums[j] ,我们根据 a 的情况讨论:
    (1)a存在,这个时候c可以接在以a、b为结尾的序列后面。设a下标为k,这里下标情况就和前面不同了,因为可能存在多个a,我们需要用一个下标数组来记录不同位置的a下标,当k < i时(a在i的前面),dp[i][j] += dp[k][i] + 1,这里的+1表示[a,b,c]这一组,把满足条件的a全部加起来即可
    (2)a不存在,这个时候只能b和c两个自己构成,dp[i][j] = 2

    我们发现,在状态转移方程中,我们需要确定 a 元素的下标。因此我们可以将所有的「元素 + 下标数组」绑定在⼀起,放到哈希表中。

  3. 初始化
    无需初始化,默认为0。

  4. 填表顺序
    填表顺序为固定倒一,枚举倒二

  5. 返回值
    定义变量sum,一边dp一边累加文章来源地址https://www.toymoban.com/news/detail-714792.html

  • 代码实现
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        //dp[i][j]表示以i,j为结尾的等差数列个数,规定j > i
        //前置可能有存在多个,需要一一加起来
        vector<vector<int>> dp(n, vector<int>(n));
        unordered_map<long long, vector<int>> hash; //数据和下标数组绑定
        for(int i = 0; i < n; i++)
            hash[nums[i]].push_back(i);
        int sum = 0;
        for(int j = 2; j < n; j++)
        {
            for(int i = 1; i < j; i++)
            {
                long long former = (long long)nums[i] * 2 - nums[j]; //处理数据溢出
                if(hash.count(former))
                {
                    for(auto k : hash[former])
                    {
                        //former必须在左边
                        if(k < i)
                            dp[i][j] += dp[k][i] + 1; //这里的1表示[a,b,c]单独一组
                        else //当前a下标不满足,后面的也一定不满足,可以直接跳出
                            break;
                    }      
                }
                sum += dp[i][j];
            }
        }
        return sum;
        //相同数据不多的情况下
        //时间复杂度:O(N ^ 2)
        //空间复杂度:O(N ^ 2)
    }
};

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

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

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

相关文章

  • 【动态规划】【二分查找】【C++算法】730. 统计不同回文子序列

    视频算法专题 动态规划汇总 二分查找算法合集 给你一个字符串 s ,返回 s 中不同的非空回文子序列个数 。由于答案可能很大,请返回对 109 + 7 取余 的结果。 字符串的子序列可以经由字符串删除 0 个或多个字符获得。 如果一个序列与它反转后的序列一致,那么它是回文序列

    2024年01月19日
    浏览(49)
  • 【动态规划】【C++算法】801. 使序列递增的最小交换次数

    【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径 动态规划汇总 数组 我们有两个长度相等且不为空的整型数组 nums1 和 nums2 。在一次操作中,我们可以交换 nums1[i] 和 nums2[i]的元素。 例如,如果 nums1 = [1,2,3,8] , nums2 =[5,6,7,4] ,你可以交换 i = 3 处的元素

    2024年01月22日
    浏览(41)
  • 【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目

    【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II 动态规划汇总 给你一个二进制字符串 binary 。 binary 的一个 子序列 如果是 非空 的且没有 前导 0 (除非数字是 “0” 本身),那么它就是一个 好 的子序列。 请你找到 binary 不同好子序列 的数目。 比方说,

    2024年02月21日
    浏览(36)
  • 【动态规划】C++算法:446等差数列划分 II - 子序列

    视频算法专题 动态规划汇总 给你一个整数数组 nums ,返回 nums 中所有 等差子序列 的数目。 如果一个序列中 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该序列为等差序列。 例如,[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。 再例如,[1, 1, 2, 5, 7] 不是

    2024年02月03日
    浏览(37)
  • 【算法(四·三):动态规划思想——最长公共子序列问题】

    最长公共子序列(Longest Common Subsequence,简称LCS)问题是一种常见的字符串处理问题。它的**目标是找到两个或多个字符串中的最长公共子序列,这个子序列不需要是连续的,但字符在原始字符串中的相对顺序必须保持一致。**例如,考虑两个字符串\\\"ABCD\\\"和\\\"ACDF\\\",它们的最长公

    2024年04月13日
    浏览(48)
  • 力扣算法刷题Day42|动态规划:01背包问题 分割等和子集

    力扣题目:01背包问题(二维数组) 刷题时长:参考题解 解题方法:动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路:两层for循环,第一层i遍历物品,第二层j枚举背包容量以内所有值 确定dp数组及下标的含义:dp[i][j] 表示从下标

    2024年02月13日
    浏览(59)
  • 力扣--动态规划300.最长递增子序列

    一开始想到的方法非常低效,但好理解。   思路分析: 使用二维数组 dp 来记录递增子序列的长度信息,其中 dp[i][0] 表示以 nums[i] 结尾的最长递增子序列的长度, dp[i][1] 表示包含 nums[i] 的最长递增子序列的长度。 初始化 dp 数组,将以第一个元素结尾的递增子序列长度置为

    2024年01月24日
    浏览(47)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(39)
  • 力扣300:最长递增子序列(Java动态规划+双指针)

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

    2024年02月12日
    浏览(46)
  • C++算法 —— 动态规划(2)路径问题

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月06日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包