2018.8.172018暑假集训关于dp的一些感想（以目前的知识水平）

学了这么长时间的dp似乎还是不怎么样

谨以此篇文字记录一年以来与dp斗智斗勇的各种经历

关于dp&＃xff08;也就是动态规划&＃xff09;似乎对于每个OIer来说都是一个永远的噩梦。

刚刚开始学dp的时候完全搞不明白&＃xff08;只是觉得好厉害的样子&＃xff09; 完全停留在刚刚好能够看懂转移方程的阶段

事实上dp这个东西和其他任何算法都不太一样&＃xff0c;同样是仅仅看不可能学会&＃xff0c;但是更加可恶的一点是&＃xff0c;你仅仅是看&＃xff0c;不仅学不会&＃xff0c;而且基本上什么东西都学不来。

说到底&＃xff0c;毕竟哪个题都不一样&＃xff0c;基本上不可能考到同样的题同样的转移方程&＃xff08;可惜当时并不明白这个道理&＃xff09;。

于是甚至在之后的几个月&＃xff0c;对于每个和dp有关系的题&＃xff0c;基本上都是看题解——想一想——就交了。。。。。。

导致在这半年中&＃xff0c;不管其他算法&＃xff0c;我的dp可以说没有半点大的进展。

直到我终于下定决心在洛谷上刷了三四十道dp之后。

所谓刷了三四十道dp&＃xff0c;不过是在看了题解之前多想了两三个小时而已&＃xff08;大家千万不要学我Q_Q&＃xff09;

尽管如此&＃xff0c;仍然是量变导致质变&＃xff0c;总算明白了一点dp究竟是啥

所谓dp这个东西&＃xff0c;其实就是状态的表示、初始化以及从一个状态向另一个状态的转移&＃xff08;废话&＃xff09;

关于书上写的那个无后效性 其实就是判断能不能用dp做‘

有很多人曾经问过我和我们一些同学dp究竟是啥&＃xff0c;说的通俗一点&＃xff0c;其实就是一个每个点只搜了一次的搜索&＃xff0c;只不过搜索的顺序比较玄学&＃xff0c;所以扯到了各种各样的状态之类的东西。

对于本人现在的水平 重点就是状态的划分

比如说01背包 就是对于每个物品的装和不装的枚举&＃xff0c;再比如说摆花&＃xff0c;就是对于每盆花摆在哪里的枚举。&＃xff08;其实很多题都可以经过多次推导变化成这两个题&＃xff0c;以后会再提&＃xff09;

很多时候会想&＃xff0c;dp的数组究竟应该怎么开&＃xff0c;开几维才能不TLE以及MLE

后来总算想起来一个方法&＃xff0c;就是枚举变量

对于我们这种水平的蒟蒻来讲&＃xff0c;一般求什么dp的结果就是什么 这是一个变量

为了方便起见&＃xff0c;我们把题目中可视的或者较为明显的称为一阶变量&＃xff0c;需要经过一阶变量推出的称为二阶变量&＃xff0c;同样的可以推出n阶变量&＃xff0c;其中包括结果在内的任何一个变量都可以是一到n阶变量&＃xff08;只要你用得比较熟练这个方法应该可以一直用下去&＃xff09;

假设我们已经根据题面初步计算出了在不会TLE及MLE的情况下最多几维dp

这样我们在选取变量作为参数的过程中就可以根据位置的个数选取不同阶数的变量进行状态的表示了

关于对状态的初始化

其实重点就是在可以手算或者心算的边界条件中选取必要的作为初始化的结果

当然还有 例如对每个状态初始值的设定用来判断状态是否有效或者对累加的设置等

关于对状态的转移

刚才已经提到过了状态的划分&＃xff0c;其实状态的转移就是从前一个状态转移到后一个状态

通常情况下&＃xff0c;对于转移方程来讲&＃xff0c;主体一定是对当前状态的操作

例如01背包的二维转移方程 dp[i][v]&＃61;max(dp[i-1][v],dp[i-1][j-w[i]]&＃43;c[i])其实就是对第i件物品“取与不取”的操作

最后再注意一下循环的顺序以及方向等细节就可以了

上述这些文字&＃xff0c;作为一年中与dp斗智斗勇的一部分经历&＃xff0c;也算是OI生涯中的一部分吧。