leetcode300.最长递增子序列(动态规划)

首先，我们来分析一下题目意思，题目给了我们一个数组nums要我们求里面最长递增的子序列的长度，但是递增的数字可以不连续的，且不能改变数组中元素的顺序。
解题思路:
这题如果我们要用动态规划去实现，首先要将该数组拆分成子问题，我拿第一个例题给大家讲一下:

如上图，我们可以先从第一个数字算起，第一个数字它自己其实就可以看成是一个递增的子序列，长度为1，因此我们可以先开一个数组，长度和该数组一样大，并且将里面的数字全部置为1，该数组的每一个下标都对应着目标数组最大递增子序列的长度，全部置为1呢，是因为一开始都还没有算长度，而数字自己本身长度就为1，接下来就是我们要怎么去计算目标数字里面每个数字的最大递增子序列的长度，然后放到存放长度的数组里面。
画图给大家理解:

代码实现:

class Solution {
    
public:
    int lengthOfLIS(vector<int>& nums) {
    
        if(nums.size()==1)
           return 1;
        int Max=0;
        int M=nums.size();
        int dp[M];
        for(int i=0;i<M;i++)
        {
    
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
    
                if(nums[i]>nums[j])
                {
    
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            if(dp[i]>Max)
               Max=dp[i];
        }
        return Max;
    }
};

运行结果如下:

这就是本篇博客的所以内容了，希望对大家有所帮助，感谢大家观看，喜欢的记得点赞关注加收藏哦!
链接如下:https://leetcode.cn/problems/longest-increasing-subsequence/