突破一。。牢记问题概念
并且牢记dp状态方程
突破二。。一直有一个求和dp转化成O1dp递推的式子看不懂。。
看不懂的原因是。。没有分清求和符号作用的范围
提醒:以后遇到求和符号一定明确其求和的式子的范围
突破三。。搞清楚这个之后我们还需要把数据变换一下。。用之前的定义中求和的式子代换回来
技巧:代换
收获四。。每一步递推都是求和式。。我们考虑它的相邻状态如何转移过来
我看的技巧是。。上一个相邻状态加上你本来所有状态减去这个相邻状态的东西。。这不是废话么。。
这个题就是把上一个相邻状态多的东西删掉。。少的东西再加上。。
这是一个减少时间复杂度的好方法。。
呵呵,但是你想不到啊,但是你想不到啊。。
技巧:a+(b-a)=b;
a-c+d+(b-a+c-d)=b;