其实感觉 像此题这种类型的并不属于dp范畴

虽然程序看起来使用的是递推这一过程，但总不能说开个二重循环就是dp吧



如果只从求解上来讲（不考虑数据值的范围), 只有枚举这唯一途径, 而此题的复杂度为O(20^20), 大约等于 10^26, 微机是很难在短时间内求解的。


而此题还有另一个限制, 就是数据值的范围, 虽然状态数那么多, 但是它们的范围有限

这个时候, 状态产生大量重复, 于是, 程序可以优化为压缩这些重复状态, 从而减少开销


在实现的过程中, 确实划分了阶段, 但这个过程更像是枚举, 优化过后的枚举

在朴素枚举当中, 阶段数与复杂度呈指数关系, 而在此题这种特殊情况下, 每个阶段数的最大不同状态数是有限的, 压缩以后就只是常数关系了


所以那 'dp'方程更像是一个'压缩状态'过程, 并没有求最优这一意思, 最后输出是状态数, 并不是最优解


再看一些常见的dp问题, 它们的意义很明确, 一定是求某种最优的结果, 其中普遍存在max,min

最为关键的一点, 凡是能够被dp的问题, 都是p类问题, 它们的复杂度都为多项式表达式

而该题类似的问题, 它们似乎往往都是npc问题, 它们很难有特别有效的算法

像本题这种就是通过狭小的数据范围来进行优化, 但仍然逃不脱枚举这一本质, 

如果稍微加大数据范围, 您看看还有更好的方法么?






当然,以上仅是自己的愚见  v_v


 

• 说得太好了，收藏了。这也是我理论上的一个纠结处啊 (749) majia_ 2009-11-14 13:04:10
• Re:此言并不差 (42) Kuroro 2012-12-06 22:25:46