常考的几类dp：背包，计数，最长子序列，路径

背包问题

可分为01背包和完全背包问题
区别是可选物品个数是一个还是无限个，这一点会在f[i]的更新上有所体现
01背包：

不选i时： f[i] = f[i-1];       直接赋值
选i时：   f[i] = f[i-1]+a[i];  只可选一次，所以状态会向前递推变为i-1，并附加条件a[i]

完全背包：

不选i时： f[i] = f[i-1];       直接赋值
选i时：   f[i] = f[i]+a[i];    因为i物品数量无限，所以也要更新f[i]的状态

没有考虑j层，因为那个变化dp都一样

初始化：因为背包问题通常都是求max/min价值，所以一般不需要初始化
状态更新时，需要确定j层不能为负数，所以就会出现分层写法：

    f[i][j] = f[i - 1][j];
    if (b <= j)
        f[i][j] = max(f[i][j], f[i - 1][j - b] + c);

其实就是考虑了背包体积的：

    f[i][j] = max(f[i - 1][j], f[i - 1][j - b] + c);

计数dp

基于完全背包问题，选或者不选某些物品，并求方案数量的题型。

初始化：通常都要考虑f[0][0]的状态，当一个物品都不选时背包体积0，也是一个合法方案，所以要初始化为1
而f[0][y]，f[x][0]不合法所以置0

状态更新时，由于同属完全背包问题，所以也要特判背包容量为负的情况

    f[i][j] = f[i - 1][j];
    if (j >= i)
        f[i][j] += f[i][j - i];

其实就是：(注意累加)

    f[i][j] = f[i - 1][j] + f[i][j - i];

最长上升子序列

不会

初始化：当只有一个数存在时，也算是一种方案，f[x] = 1;

DP问题：
注意一件事情：DP问题分为两种形式，三种条件
两种形式是f[i]和f[i][j]
    如果是一维，一般使用forfor遍历所有答案
    如果是二维，基本是路径问题，一般使用forforfor对xy遍历，再遍历条件

三种条件是MAX,MIN,COUNT
    前两种的更新方法一般是f[i]=max(f[i],f[i-1]+w[i]);
    后一种一般是f[i]+=f[i-1]+w[i];

通常使用f[i]表示当前位置i满足某种条件的状态，并且从后向前推f[i-1]的状态
虽然思路上是从后向前递推的，但实际上代码是从前向后，为了将答案从f[i-1]累计到f[i]上面(反过来就不行)
注意，不代表f[n]就一定是答案，因为n点不一定符合条件

甚至可以将简单DP问题解释为披着forfor双指针的皮，使用f[i]记录状态
如果f[i]和f[i-1]满足某种关系，就可以化为一类f[i]=f[i-1]+w[i];
如果不满足，跳过就好，反正是一定要初始化的

比如895最长上升子序列问题
输入序列        a[] = 3 1 2 1 8 5 6
所求状态        f[] = 1 1 2 1 3 3 4
从前向后遍历，更新f[i]

例如：求2156上升子序列，n=4
i=4，f[i]向前找f[i-1]的解有：   
2-6：a[1]-a[i]，f[i] = 2
                            1-6：a[2]-a[i]，f[i] = 2
                            5-6：a[3]-a[i]，f[i] = 2
                            6-6：a[4]-a[i]，f[i] = 1  本身就只有初始化的1

向前推，此时f[i]=f[i-1]，而f[i-1]的解有:   
2-6：a[1]-a[i]，f[i] = 2，没有更前的了
                                        1-6：a[2]-a[i]，f[i] = 2，有2-1-6但不合条件
                                            5-6：a[3]-a[i]，f[i] = 2时：
                                            2-5-6：a[1]-a[3]-a[4]，f[i] = 3
                                            1-5-6：a[2]-a[3]-a[4]，f[i] = 3
所以答案是3，可以看出forfor的次序是从头到尾的，而且不影响答案