对于挑战书上的很久之前都看不懂的DP看懂的突破

时间:2024-10-11 21:05:20

突破一。。牢记问题概念

并且牢记dp状态方程

突破二。。一直有一个求和dp转化成O1dp递推的式子看不懂。。

看不懂的原因是。。没有分清求和符号作用的范围

提醒:以后遇到求和符号一定明确其求和的式子的范围

突破三。。搞清楚这个之后我们还需要把数据变换一下。。用之前的定义中求和的式子代换回来

技巧:代换

收获四。。每一步递推都是求和式。。我们考虑它的相邻状态如何转移过来

     我看的技巧是。。上一个相邻状态加上你本来所有状态减去这个相邻状态的东西。。这不是废话么。。

      这个题就是把上一个相邻状态多的东西删掉。。少的东西再加上。。

      这是一个减少时间复杂度的好方法。。

      呵呵,但是你想不到啊,但是你想不到啊。。

技巧:a+(b-a)=b;

   a-c+d+(b-a+c-d)=b;