动态规划27：300. 最长递增子序列

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：

题解：

1.状态表示：dp[i]表示以nums[i]结尾的子序列中最长严格递增子序列的长度

2.状态转移方程：见代码分析

3.初始化：dp表最低值为1，所以在创建dp表时可以将所有的值都初始化为1

4.填表顺序：从左向右依次填写

5.返回值：返回dp表中的最大值

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //dp[i]表示以nums[i]结尾的子序列中最长严格递增子序列的长度
        //状态转移方程：
        //如果nums[i]大于其前面的某个值nums[j]
        //才有可能存在长度大于1的严格递增子序列
        //所以遍历其前面的值，找到比nums[i]小的值，此时dp[i]=dp[j]+1
        //但是比nums[i]小的值可能不止一个，所以要去最大的值dp[i]=max(dp[i],dp[j]+1)
        //如果nums[i]比前面的所有都小或者等于
        //那么以nums[i]子序列结尾的严格递增的子序列只能是nums[i]本身
        //dp[i]=1
        //综上所述
        //可以先将dp表初始化为最低的值，即1
        //if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1) 0<=j<i

        size_t n=nums.size();
        //处理边界条件
        if(n==1) return 1;
        //创建dp表
        vector<int> dp(n,1);//先将dp表初始化为最低的值，即1
        //初始化
        dp[0]=1;//可省略了
        //填表
        for(int i=1;i<n;++i)
        {
            for(int j=0;j<i;++j)
            {
                if(nums[i]>nums[j]) 
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        //返回值
        int ans=0;
        for(auto e:dp) if(e>ans) ans=e;
        return ans;
    }
};