最长上升子序列

问题描述
最长上升子序列( LIS ) 定义
给定长度为n的序列，从中选取一个子序列,这个子序列需要单调递增。问最长上升子序列( LIS )的长度。eg : 1, 5, 2, 3, 11, 7, 9则LIS序列为: 1, 2, 3, 7, 9 。则长度为5

设计状态
记f(x)为以a[x]结尾的LIS长度,那么LIS=max{f(x)}。
如何推导f(x)，f(x)从哪里来?
考虑比x小的每一个p，如果a[x] > a[p]，那么f(x) = f(p) + 1
状态转移方程
f(x) = max(f(x), f(p)+1)，    （p<x，a[p]<a[x]）

哪些题目适合用DP算法解决?如何设计好DP算法:
1.满足最优子结构
大问题可以由小问题推出，大问题与小问题求解思路一致。
2.满足无后效性
一旦f(n)确定，后续我们直接调用它的值就可以,而不用关心它是怎样过来的
3.设计好状态
想办法把当前局面给表达出来
4.设计好状态转移方程
可以从两个方面考虑，我从哪里来，或者我到哪里去
5.代码实现（只有核心代码，输入省略了）

int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        int ans = 1;
        vector<int> dp(len, 1);
        for(int i = 0;i < nums.size();++i){
            for(int j = 0;j < i;++j){
                if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
 }

注：个人水平有限，写得也粗略，但方法和代码正确，若有问题，请评论指教，谢谢支持，共同进步。