（动态规划）leetcode-300. 最长递增子序列_leetcode-最长递增子序列-动态规划

题目链接：力扣

本题很显然能用动态规划解。设以在数组nums]中，以nums[i]为结尾的最长严格递增子序列长度为p[i]，则有以下状态转移方程：

p[0]=1

p[i]=max(p[j]+1)，其中0<=j<i<n且nums[i]>nums[j]

即： 对于所有比i小的数j，如果有nums[i]>nums[j]，则以nums[j]为结尾的递增子序列再加上i，还是一个递增子序列；在i的所有这样的递增子序列中，找到长度最大的那个，就是以nums[i]为结尾的最长递增子序列。代码如下：

class Solution {
public:
 
    int p[2510]; //结尾为i的最长递增子序列长度(0<=i<n)
 
    void init(vector<int>& nums){
        p[0]=1;
        for(int i=1;i<nums.size();i++){
            int max=1;
            for(int j=i-1;j>=0;j--){
                if(nums[i]>nums[j] && max<p[j]+1) max=p[j]+1;
            }
            p[i]=max;
        }
    }
 
    int lengthOfLIS(vector<int>& nums) {
        init(nums);
        int max=0;
        for(int i=0;i<nums.size();i++){
            if(p[i]>max) max=p[i];
        }
        return max;
    }
};

时间复杂度: O(n2)

空间复杂度: O(n)