DP大楼

admin

最简单的是递推，后面的由前面的几个计算得到，比如：等差等比数列，二阶等差，斐波那契，杨辉三角，卡特兰数，斯特林数等，不涉及比较，直接硬推。   
注意这个推的过程，有的是一次就可以搞定，有的需要几轮。
P1077 摆花  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36070
P1057 传球游戏 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36069
连环炸弹  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36049

比这难一点的是每次决策过程中不是简单的累加而是有比较，比如
筷子  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36143
最长不下降序列LICS  导弹飞机  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3659
P1233 木棍加工 LICS改进 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36205
P1650 田忌赛马 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36144
P2725 邮票 Stamps  http://hsyit.cn/forum.php?mod=viewthread&tid=36027

再复杂一点的就是二维表DP  要多次扫描，一轮轮的，简单的就是填一个表的过程，注意细节。当然有的可以迭代或者使用滚动数组变成一维数组但是本质还是多轮推。  
杨辉三角 （滚动DP） 这里要认真体会二维数组做法，滚动数组，和反向数组递推的做法 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36058
数字三角形  http://hsyit.cn/forum.php?mod=viewthread&tid=36405
乘积最大  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35999        
最大的算式  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36055
最长公子序列     回文串  最长公共子序列的变形使用  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36212
相似基因
   

经典背包问题  它也算二维表型DP，注意我的那个推导过程， 特别是如何用一维数组的。

基础背包采药  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36061
疯狂的采药  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36000
开心的金明  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35890
金明的预算 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36060

背包加强版
P1794 装备运输  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36146
P1509 找啊找啊找GF http://www.hsyit.cn/forum.php?mod=viewthread&tid=36134
氧气瓶氮气瓶    http://www.hsyit.cn/forum.php?mod=viewthread&tid=36015
P2736 “破锣摇滚”乐队 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36147
P1095 守望者的逃离  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36003
P2725 邮票 Stamps http://www.hsyit.cn/forum.php?mod=viewthread&tid=36027

P1782 旅行商的背包 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36002

很难的背包P1757 通天之分组背包  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36148


区间DP
P1063 能量项链 http://www.hsyit.cn/forum.php?mod=viewthread&tid=3669
P1880 [NOI1995]石子合并 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36126

树上DP
P1040 加分二叉树  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36150


状压DP
http://hsyit.cn/forum.php?mod=viewthread&tid=36305

admin

数字图形及其变形类
1、杨辉三角
2、数字三角形  P1216 [USACO1.5]数字三角形 Number Triangles
3、方格取数  P1004 方格取数
4、

admin

简单背包类DP
采药装箱


开心的金明
砝码问题