1.dp[i]的定义

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2.状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3.dp[i]的初始化

每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4.确定遍历顺序

dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

代码

class Solution {
public:
    const int N = 2510;
    int lengthOfLIS(vector<int>& nums) {
        int f[N];  // f[i]表示当前末尾为nums[i]的时候，最长子序列长度
        for( int i=0; i<nums.size(); i++ ) f[i] = 1;  // 自己长度

        // 理解递归顺序：从小到大，依赖于前面的状态
        for( int i=1; i<nums.size(); i++ )
        for( int j=0; j<i; j++ )
        {
            if( nums[i]>nums[j] ) f[i] = max(f[i],f[j]+1);
        }
        int res=0;
        for( int i=0; i<nums.size(); i++ ) res = max(res,f[i]);
        return res;
    }
};