ACM习题集

DP ?

什么是”0-1 背包” 和” 完全背包”

这两天我们一起在学校集训做 DP 的专题,做了这么几天,我觉得,DP 这东西是真的不好想。首先,是什么样的问题可以用 dp 来解决。我觉得有一下这么几种吧

  1. 题目中的问题,随着某项属性的变化而变化,比如随着时间的变化。其实这就是说可以划分出子问题,比如考虑整个字符串和部分字符串,考虑全部区间还是部分区间,考虑所有物品还是前多少件物品。
  2. 可以找到明显的状态变化公式。
  3. 拥有已知的 dp 模型

dp 问题感觉比较难看出来,但是一般区间选择,字符串处理, 背包问题会经常遇到。不求看见一个问题就知道可以用 dp 来做吧,但求这些遇见过的类型自己再次遇见时能看出个大概来,只要不是脑袋发热啥都看不出来就行了。

难点

  1. dp 数组的定义,也就是要记录什么样的状态。
  2. dp 边界条件的设置。
  3. dp 的递推公式。

还是要多做题啊

搞这东西真的是需要思维灵活才可以啊。很不喜欢搜题解的感觉,因为感觉自己在抄别人的东西,没有成就感,这几天做的题如果不复习我相信没过几天就会忘了。希望过几天自己能不参考题解重新再做一遍,真正的掌握 dp。

另外关于题解,我不会把具体的题目题解放到这上面的。我还是选择用一个和源代码同名的 markdown 文件来存储题解,和源代码一同放置在伟大的 GitHub 上 23333

这是一个例子 DP_Balance 题解