最长递增子序列（动态规划）c++

题目描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

递推式：（考虑题目问什么，就把什么定义成状态。dp[i] 表示：以 nums[i] 结尾 的「上升子序列」的长度。）

初始化注意：dp[i] = 1，11 个字符显然是长度为 11 的上升子序列。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=nums.size();
        int dp[len],result=0;
        dp[0]=1;
        for(int i=1;i<len;i++)
        {
            dp[i]=1;//这里注意一定是初始化为1
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])//注意这里比较的是nums
                    dp[i]=max(dp[i],dp[j]+1);  //递推式            
            }
            
        }
        for(int i=0;i<len;i++)
        {
            result=max(result,dp[i]);//结果需要循环找最值，而不是dp[len-1]
        }
        return result;
    }
};