300.最长上升子序列的长度

思路：
动态规划

思路解释：
1.这里的动态规划的应用与以往不同，以往是直接求结果，而这里采用的方案是dp[i]代表从[0..i]中去选择，并且一定选中i号元素。
2.之所以这样设计是因为这样解题的逻辑会很简单，只需要比较一下当前数字比之前大的数字就行，比之前大，那么长度就一定比之前的多1，依次类推。
3.要注意的是因为返回的结果是选中i后从[0..i]的最长上升子序列的长度，并不是最终结果，所以最终结果还要遍历一遍

代码实现：

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