leetcode 300.最长递增子序列

动态规划的经典问题之一。

思路：这里的dp数组定义与之前做的那个打家劫舍得模板不一样，上一个计算的是偷多少家获得的最大钱财，是对于房子个数的定义。这里并不是，这里是对于一个数结尾作为dp数组的定义。

解释一下，我们首先拿3，1，2，0，5作为例子。这里的最大递增子序列是1，2，5.。有人这个时候想用暴力做了。不对，如果是1，2，3，2，3，5呢？你的暴力解法就不管用了，会卡在第一个3上，所以不可取。

这里作尾的思想大家作为一种思想记住，动态规划的最好办法就是积累，当然不排除你自己天赋异禀。作尾的话我们就可以递推来实现了。就拿第一个例子说，我们拿3作尾，这个时候就只有一个；如果拿5作尾，我们从头开始遍历，{3，5}j是，以3作尾的子序列也并上来了，这是一种可能，{1，2，5}是一种，以2作尾的序列也并上来了，也就是{1，2}，以1作尾的序列也并上来了，也就是{1}。这样大家应该就清楚了，我们需要的最长递增序列，需要的就是各种数字作尾相连接起来！同样，我们以5作尾本身就有序列，需要上一层保险，跟前面接上来的序列加上这个5作比较。

这样就写出来了状态方程：

dp[i]=max(dp[i],dp[j]+1)

注意：为什么在最后+1？因为我们原始令dp为0了，你可以令dp初始值为1,这样就不在最后+1了，就是考虑到自身作尾的数也算数。

上代码：

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