前言
本身我自己dp学的就不是很好，现在刷几道题有关dp的，每道题总结一下做题的思路。
P2871 USACO07DEC]手链Charm Bracelet
这是一道01背包题，很基础, dp[j]表示的是背包里已经有i的重量，所能拿到的最大价值， 考虑枚举每一个物品， 考虑拿或者不拿，枚举最大重量到本物体的重量， 如果拿的话， 那么当前的重量所能拿到的最大值是dp[ j - w[ i ] + c[ i ], 如果不拿的情况下， 当前的最大重量为dp[ j ], 在这两个之中取最大值就好了， 答案就是dp数组中存的最大的那一个。
为什么第二重循环枚举重量要从后往前枚举：
当j值从 w[j] 枚举到 V 的话， 如果dp[ j - c[ i ] ]被更新掉的话， 那么如果 V 是c[ i ]的倍数或者更大的话， 那么dp[ j - c[ i ] ]将会被转移两次。所以这就成了完全背包了， 但是如果从后往前更新的话就会避免dp[ j ]重复计算的事情发生。
P2639 [USACO09OCT]Bessie的体重问题Bessie’s We…
这是一道装货问题， 也可以看成一道01背包问题， 只不过每一个物品的花费也是这个物品的重量， 转移方程是：f[ j ] = max(f[ j ], f[ j - w[ i ]]+w[ i ]);
P2722 总分 Score Inflation
这又是一道裸的 01 背包问题， 交板子就好。
P2347 砝码称重
考虑这是一道多重背包的问题，给出每一个物品的价值， 和每个物品的个数。但是不同的的是他让求的是方案数， 可以考虑把这道题转换为一个 01 背包来做， 把每一个砝码有的个数拆开， 转换为共有a[ i ]个价值为w[ i ]的物品来跑一遍 01 背包的dp就好了， 但是需要注意的是一个思路的转换， 有一个bool数组来表示第 j 个是否可以被测量出， 于是就从后往前跑一遍， 如果当前的 j 是可以测量的， 那么把现在这个砝码加上的重量也是可以测量出的， 就是dp[ j + w[ i ]]这个也是可以测量出的。 注意一下边界条件， 因为是 j + w[ i ] ，所以将dp[ 0 ] = true。 最后从1跑到最后一下统计方案数输出就好了。
P2925 [USACO08DEC]干草出售Hay For Sale
这又是一道水题， 看完之后这不就是一个 01 背包吗， 贼稳， 然后就TLE了一个点， 很难受， 看完题解之后发现会被卡一个点， 解决方法就是一个特判， 当dp[ C ] 已经被装满的话直接输出然后退出程序。
p1060 开心的金明
一个最简单的0/1背包问题， 物品的价值如题义。
p1164 小A点菜
注意方案数的 dp 一般是采用 F[i] += F[i - w[i]] 的递推模式， 而并不是采用求最优解的 max(F[i], F[i - w[i]]) 这种方式。
p1064 金明的预算方案
这是一道有依赖的背包， 因为最多带两个附件， 进行分类讨论即可，0/1背包的变形
p1091 合唱队形
LIS问题， 一个思想的转变， 从前到后求一遍LIS， 然后从后往前求一遍LIS， 枚举每一个点， n - f1[i] - f2[i] + 1就是最少的出列人数。
p1616 P1616 疯狂的采药
完全背包问题，板子题
p1280 P1280 尼克的任务
一道线性dp， 把每一个任务看做一个阶段， 第 j个任务可以用来更新的标准是 ：
1 | 1. 当前任务的结束时间比第 i 个任务的开始时间要早； |
于是我们可以维护一个 f[ i ] 数组表示第 i 个任务开始之前最长的空闲时间， 维护一个 b[ i ] 来表示第 i 个任务最近的下一个任务 开始的时间。如果第 i 个任务可以来更新这个任务的话， 那么来比较一下大小， 进行更新。
p1880 P1880 [NOI1995]石子合并
一道区间DP， 洛谷的题经过改动， 由原来的一条链改成了一个环。 解决方法就是直接把 a 数组直接复制一份接到a的后面， 然后当成一条链做， 长度的枚举还是不变， 但是端点的枚举的范围变成 2n 。在寻找最佳答案的时候寻找 f[i][i+n-1] 这样的解中的最优值即可。题解链接
p1063 P1063 能量项链
又是一道区间DP， 又是一个拆环成链的一个DP， 转移方程较水， 和石子合并的思路差不多， 水题。
p1140 P1140 相似基因
是一道很像 LCS 的一道题， 主要是需要考虑 a[i] 与 b[i]的贡献值， 需要用一个表格来记录不同的对应情况所得的值， 然后和 LCS 一样跑一遍即可
水题到此结束
P2858 [USACO06FEB]奶牛零食Treats for the Cows
怎么说.. 原来的思路是不对的， 想了一会没结果就看题解了。正解是一个区间DP，一个数组DP[i][j]表示选择了i,j区间内的零食所能达到的最大值。状态转移方程是这个样子的：
1 | dp[i][j] = max(dp[i+1][j] + v[i] *(n - l + 1), |
式子的含义是枚举的区间开始和结尾的值选择哪一个最大的，区间dp的小技巧就是不要直接枚举区间的开始和结束，而是枚举一下区间的长度，和开始， 然后算出结束的坐标。
初始化：
有关于这个dp数组的初始化应该为dp[ i ][ i ]为最后一个选择的，即长度为1的区间的最大价值为最后一个选择时的最大值。