动态规划虽然难，它的一般题目也是有规律可循的。从这一讲开始，我们会归纳几种具体的题型。大概会分为以下几讲：

一维情况下的动态规划，其典型题型就是最长递增子序列
从最长递增子序列出发，涵盖它的各种变形题目
介于一维和二维的中间情况，即虽然是二维的题目，思路和一维下是一致的。代表是染色问题
对称情况下的二维问题，代表是编辑距离问题
非对称情况下的二维问题，代表是背包问题
博弈问题
递推问题
那么，我们就从最基础的题型开始讲解。本讲要讲的一维问题会给出一个一维的数组。每一个数组的位置就是一个状态A，表示，取了这里的元素之后的解的情况。在搜索的过程中，之后的每一个点B都要找一个前置点，通过对比更新B点的状态。

这里面讲得最多的，每一篇将动态规划的文章都会提到的，就是最长递增子序列：

1. Longest Increasing Subsequence（Medium）
   有一个数组 nums, 返回最长的严格递增子序列的长度。
   子序列的定义是可以删掉一些元素，保持剩下的元素序不变。比如[3,6,2,7] 就是 [0,3,1,6,2,2,7]的子序列。
   样例 1:
   输入 nums = [10,9,2,5,3,7,101,18]
   结果: 4
   解释: 具体的子序列是 [2,3,7,101], 它的长度是4.
   这道题目的状态定义为，当我们从左往右抵达元素i的时候，并且选择了i组成子序列，此时的最长长度。那么在我们又访问后面一个元素j的时候，可以比较i和j，如果nums[j]>nums[i]，那么j就可以附在i的后面组成新的递增子序列。在这个过程中j不需要考虑i再往前的情况，因为那些情况都已经被i压缩在自己的状态中了。这道题目之所以存在状态压缩，是因为大小关系是可以递推的，j比i大，那么就一定比i中所选的子序列的前一个大，以此类推。但是在时间上，这类问题不容易节省，j其实要访问它前面的所有可能的i，才能知道自己的最长选择是什么。因此这个做法下时间是 [公式] 的。

int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> s(n,1);//1
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){//2
                if(nums[i]>nums[j]) s[i]=max(s[i],s[j]+1);//3
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res=max(res,s[i]);//4
        }
        return res;
    }

s就是我们的状态数组，这里把初始值默认为1了，因为每个元素至少都可以取自己
代码中符合一般的习惯，和上面的i，j是相反的，i遍历所有，j仅仅遍历i之前的元素
状态转移的过程
注意最后的结果有可能是以每一个元素结尾的子序列
但其实，这个题目还存在 [公式] 的解法。这里直接展示把，也是看讨论区的，理解起来需要费一番功夫。我们设定一个新的数组tails，第i个元素表示的是长度为i+1的子序列，最后结尾的最小值。比如[1,3]，那就转化成tails[1]=3，如果还存在[1,2]，那么就得改为tails[1]=2. 首先我们可以指出，这个数组是单调递增的。因为当你的子序列长度更长时，结尾元素不可能更小吧。接下来我们可以遍历每一个元素，然后去二分查找tails数组。如果它小于某个长度下的tail的值，那么就替换掉tail的值，这样结尾更小，更有利于后面组成长序列。如果所有的tail值都更小，那说明这时候不是替换，而是必须得增加长度了：

int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> tails(n,0);
        int l=0;
        for(int i=0;i<n;i++) {
            int p1=0, p2=l;
            while(p1<p2){
                int mid=(p1+p2)/2;
                if(tails[mid]<nums[i])
                    p1=mid+1;
                else
                    p2=mid;
            }
            tails[p1]=nums[i];
            if(p1==l) 
                l++;
        }
        return l;
    }

掌握这种题型的最好办法就是马上再看一道，几乎一模一样的题目：

1. Maximum Length of Pair Chain（Medium）
   这次不是数组，而是n个pair，可以看做区间： pairs[i] = [lefti, righti] 其中 lefti < righti.p2 = [c, d] 跟随 p1 = [a, b] 指的是满足b < c.根据这个规则可以得到一长串。返回能够形成的最长串的长度。注意不一定要按照从左到右。
   样例 1:
   输入: pairs = [[1,2],[2,3],[3,4]] :
   结果 2：
   解释: [1,2]连接[3,4]
   这道题目和上一道题目相比，区别就在于没有从左往右这个顺序了。这个时候我们可以对pair进行排序，虽然不能100%保证，但这样一来大多数左边的pair就可以被右边的pair跟随。排好序之后的结果完全可以按照从左到右来访问。

int findLongestChain(vector<vector<int>>& pairs) {
        int n=pairs.size();
        sort(pairs.begin(),pairs.end());//1
        vector<int> s(n,1);//2
        int res=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(pairs[j][1]<pairs[i][0]){//3
                    s[i]=max(s[i],s[j]+1);
                }
            }
            res=max(res,s[i]);
        }
        return res;
    }

先进行排序，然后再从左往右访问
状态同上
题目中描述的跟随条件
其他部分和标准的最长递增子序列是一样的。