0:
靠前感觉之前dp抄题解都是抄的题解,自己从没有真正理解过dp。wyh下了很大决心从头学dp,于是便有了这篇文章。
1.背包
前四讲01背包&多重背包&完全背包(混合背包) :樱花
(Note:) 还需要学单调队列优化多重背包。
其他:咕咕咕!
泛化物品:
应该说是背包问题的一个方法综合,以函数的眼光审视背包,有助于新类型背包问题的解决。
考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。
更严格的定义之。在背包容量为V的背包问题中,泛化物品是一个定义域为0..V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)。
2.简单 pj 组 dp:
这是一道区间dp的模型,可以延伸出许多变形。
这是一道二维dp的模型,唯一讨厌的是高精。需要注意的是算边界,由于wyh很菜,所以经常算错,还不爱调。
四维dp,就喜欢这样的题,既不用算边界,也不怎么用调qwq
算边界仍然是老大难,而且对于这种方程的状态及转移还是很不熟练。
状态还是不感冒,还有,一定要读懂题在做,一定要读懂题在做,一定要读懂题在做!!!不要问我为啥强调。。。
应该先看看当前状态需要用到哪些状态,从而确定循环的顺序以及边界。
边界不光确定在循环中,有时在方程中也存在边界问题。。。
两条路径不交插的模型需要
而不是
所以,不要自作聪明,不要想当然,每一个细节都要模拟好。
dp状态不合法的最好不遍历到,因为像wyh这种智商是想不到赋最值来避开不合法状态会发生什么的qwq。inf+1=-inf。
我需要一个好的dp状态,啊啊啊啊啊啊啊wyh智商咋那么低啊啊啊崩溃了啊啊啊啊啊啊啊!
设 (f_{i,x}) 表示 (i) 个苹果放在 (x) 个抽屉里。第一种情况是有一个抽屉放一个苹果,即 (f_{i-1,x-1}),第二种情况是保证没有抽屉放一个苹果。就是把每一个抽屉都先放上一个苹果,然后还剩 (i-x) 个苹果。所以方程是:
(估计连智商低的我都能看懂的解释就不能再详细了 qwq
简单的 dp 就是要考虑当前状态根据之前的状态转移过来,并且大多数要考虑 i-1 的情况。
3.树形 dp 入门:
(未完待续,等待Update,,,