本文针对动态规划的常见类型进行总结。虽说总结的是动态规划，但顺便把递推也放了进来。严格来说，递推不属于动态规划问题，因为动态规划不仅有递推过程，还要有决策（即取最优），但广义的动态规划是可以包含递推的，递推是一类简单的、特殊的动态规划，毕竟动态规划与递推密不可分。动态规划类型主要分为纯粹动态规划问题和复合动态规划问题。

几点说明：

1、博主本人于2012年对信息学竞赛中的动态规划问题进行了总结，最初以名为《NOIP的DP总结之DP类型》的文档上传至百度文库（当然题目难度不限于NOIP，还包括NOI甚至IOI级别较难的题），时隔6年，决定将该总结以博客形式发表，并且原文内容不进行改动。

2、本总结中，涉及不少题目及其解题报告的原版照抄，但部分题目无法查证原始出处，本着以分享的目的写入总结，若有不当之处，还请包涵；若实在不妥，可请指出，本人尽快纠正不当之处。

3、总结中涉及的不少题目未加描述，读者可自行百度搜索题目名，建议搜索关键词加上“动态规划”或“DP”。

4、总结中涉及的代码为Pascal语言，因总结之年代久远，烦请见谅；代码是相通的，理解代码的思路即可。

目录

一、资源型

01背包

完全背包

多重背包

二维费用背包

分组背包

有依赖的背包

泛化物品

背包问题的经典变形

背包问题的搜索方法

崔天翼大牛推荐的相关题目（USACO）

其他

二、线性动态规划

三、区间动态规划（剖分问题）

四、坐标动态规划（平面、地图）

五、树型动态规划

六、字符串动态规划

七、贪心动态规划

八、多进程动态规划

九、状压动态规划

十、判定型动态规划

十一、目标型动态规划

十二、概率动态规划

十三、二次动态规划（双重动态规划）

十四、递推问题

十五、计数问题

主要是背包问题，背包部分的资料来源主要是《背包九讲》，另外也有自己的一些补充。 背包部分可以添加个叫“+-1背包”的家伙（属判定型动态规划）；其次还有机器分配类问题。

这个是最基础的。

首先要注意问法，是否必须完全装满，若是，则初值除f[i,0]=0外全赋值为负无穷。

空间优化：二维变一维，注意枚举顺序要变为downto（倒序枚举）！

时间优化：内层枚举的下界取 max{V-sum{w[i..n]},c[i]}

相关题目：01背包母题，采药，poj2184，poj1882，poj1252，poj2063，poj1717，poj1203

变形：

1 判定性01背包：

装箱问题，石子归并（装half箱），补圣衣，挤牛奶，积木城堡

2 多包限制顺序型01背包：

USACO Raucous Rockers

（多个背包，不可以重复放物品，但放物品的顺序有限制。）

F[I,j,k]表示决策到第i个物品、第j个背包，此背包花费了k的空间。

f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t]+p)

空间优化：变为一维。注意顺序枚举。（对应于时间优化4）

时间优化（前3个其实都用不上，只是了解下思想）：

1 若两件物品i、j满足c[i]=w[j]，则将物品j去掉，不用考虑。首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V+N)地完成这个优化。这个优化一般作用较小，非常必要时再用。

2 转化的思想（此处未优化）：将物品i拆成V/c[i]个。

3 更高效的转化方法是：把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k