准确来说，动态规划是一种思想，而不是一种算法。算导里将它归结为——高级程序设计技巧。

  在线性结构上进行状态转移DP，统称线性DP。

  线性DP最常见的有： 子集和问题，LIS问题，LCS问题。

  拓展之后有：子段和问题，杂类问题。

1. 子集和问题和硬币计数问题

子集和问题的一个实例: 〈S,t〉。其中，S={ 1 x ， 2 x ，…， n x }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得s1中的各元素之和等于c。 这其实就是0/1背包。

硬币计数问题的一个实例：给出n个正整数组成的集合{a1，a2....an},ka1+ka2+ka3+...kan=T有多少解? 这其实就是0/1背包计数。

背包问题的早期总结来自于dd_engi的背包九讲。其中属于线性DP的部分为：0/1背包，完全背包，多重背包，混合背包，分组背包，二维费用背包。

计数问题的循环和转移方程和背包问题都非常相似。

@练习题。

HDU 1864，浮点数0/1背包。先对价格做个转化，不然没法数组转移。

ZOJ3211，贪心0/1背包，首先可以肯定的是，要满足最大，每天肯定都得取。由于每棵树增长快慢不同，所以肯定先砍增长慢的，后砍增长快的，权值(j-1)*b+a。

HDU 1114，最小化完全背包，初始化全部为inf，转移条件从max改为min。特判条件两个：f[V]>=inf代表不可能装满，V=0代表空背包。

这题同时也牵扯到最大化背包的初始化问题，如果要求装满背包, 则f[0]=0,f[1..V]=-inf。

HDU 1712，分组背包。N天，M节课。对于每一天，可以选择1...M之间任何一节课。注意for(V)循环在for(组）循环外面，才能保证每组只有一个被选。

POJ 1276，多重背包。

HDU 1171，多重背包。尽可能将总价值半分，先用V/2背包一次，这个结果是最接近V/2的，然后另一个就是V-f[V/2]了。

HDU 2844，多重背包可达。需要求的是可以凑出多少种面值。由于钱币的特殊性（val=cost），所以背包完了之后，判断f[i]=i的个数即可。

POJ 1014，多重背包可达。判断一堆石子能否分为价值相等的两堆。特性val=cost，判断f[V/2]是否等于V/2即可。另外V是奇数可以不用计算。

UVA 147，完全背包计数。循环倒过来，根据基础面值压缩一下全部面值。

HDU 5000, 分组背包计数。2014鞍山网络赛D题，一个神奇的结论，把所有T值加起来/2就是背包容量，然后每组物品就是0~T[i]，注意0值物品不要选，是没意义的，实际上是从1~T[i]。WJMZBMR说其实用分组背包是TLE的，这题比赛时候就放水了,T^T。至于结论证明，orz不会。

2.LIS问题

     LIS 的转移方程f[i]=max(a[i],f[j]+a[i]),其中j的范围是1...i-1，常规是扫一遍O(n),借助二分查找可以O（logn）， 也就是所谓的二分优化。LIS分为单维度，和双维度两类。单维度直接DP，双维度需要先sort，让其中一个维单调，然后对另一个维DP。

POJ 2533，裸题，可以练习二分优化的使用。

POJ 1609，双维度LIS。铺砖头，新的砖放旧的砖上面，必须满足l>=l‘,m>=m‘,先对l排序，然后对m DP。注意本题的第一维可以相等。如果要求不等，则DP条件里还要对l维特判，如Vijos 1336。

POJ 3616，双维度LIS。挤牛奶，多个时间段，要求不能重叠，且挤完后休息r时间。先对开始时间排序，然后对结束时间DP。条件由原来的递增改为j.end+r<=i.start。

Vijos 1303，单维度LIS。导弹拦截，第一问是LDS，第二问是LIS。第二问是LIS的原因是，只要单调增就得+1，所以LIS是正确的。LIS+LDS=n，俩个正好互补。

Vijos 1336，双维度LIS。看起来像个迷宫DP，其实不是。想要距离最短，就得尽可能走特殊边。但是特殊边是有要求的，后一个特殊边x>x‘,y>y‘，DP即可。

线性动态规划