POJ2353
穷逼DP时间复杂度O(n*m*m), 我想的就是这个..
牛逼DP时间复杂度O(n*m), 每一个room的状态都只能由左下右三个room决定, 从底向上双向递归..

POJ3612
把dp[i][h]分成两部分求解, 两部分可以分别以O(100)预处理, 求dp[i][h]是O(1), 所以整个复杂度只有O(n*100), 很棒
引用牛kevin0602的讲解(他的博客已经进不去了.. 不知为何)

先分h’大于h和小于h两种情况，这方程可写为f(n, h) = (H[i]-h)^2 + min { -C*h + min { f(n-1, h’)+C*h’ } (for h’ >= h),C*h + min { f(n-1, h’)-C*h’ } (for h’ < h) }，这样就把h’放在一起了，现在定义low(n, h) := min over h' >= h { f(n, h’)+C*h’ }，high(n, h) := min over h’ < h { f(n, h')-C*h' }，则可方程进一步写为f(n, h) = (H[i]-h)^2 + min { -C*h+low(n-1, h), C*h+high(n-1, h) }。在计算第n个电线杆的时候，low(n-1, h)和 high(n-1, h)用双重DP的方法可以在O(100)*3的时间内算出，则总时间复杂度为O(N*100)。

双向DP有点类似双向BFS, 两次BFS后可以O(1)求通过某点的入口-出口路径, 这两个题每一个状态都是可以表示成从两个状态比较来. 以后遇到类似的题目要警觉一下.. 或许还有三向之类的衍生..

代码:
Continue reading →