动态规划优化.ppt

浅谈动态规划优化
2009曹文信息学奥林匹克夏令营
Author: Will
简介
动态规划优化的主要方法:
1、降维(优化状态)
2、优化转移
3、常数优化

降维是一个通用的说法,其实质就是通过改变动态规划的状态含义,或者抛弃一些冗余状态环节,达到减少状态,加速动态规划的目的

很多时候,当得出某种动态规划模型的时候,不要着急动手,而是需要仔细思考一下,是不是有更好的状态表示方法
多积累经验,同时又不能拘泥于死板的模型理论,要有创新意识。

给定N*M的空白棋盘,在其中放任意放车(可以不放),要使得放在棋盘上的车两两不能攻击,求方案总数MOD P的值。

按照基本的状态压缩动态规划模型进行解答。
opt[K][S]表示已经放了前K行,并且每一列是否有车的状态为S(S为一个0/1的2进制序列,那一位为1则表示对应一列已经放过了一个车)的合法方案的数量。
比如opt[2][(101)2]即表示前2行放了车且第1,3列有车的状态。

则转移就是枚举这一行放还是不放,如果放的话则枚举所有没有放车的行,将对应的2进制位标记为1,进行转移。
时间复杂度O(NM2M)
空间复杂度O(2M)
但是……
如果N,M>1000该怎么办呢?

换一个角度来分析问题
可以发现,我们需要知道的只是有多少列目前没有放车,并不需要知道具体是哪些列没有放车!
因此opt[k][(101)2]和opt[k][(110)2]是本质等价的。
于是我们可以把状态改为:opt[k][S]表示放置了前k行,并且有S列没有放置。

此时转移稍有不同
opt[k+1][S]=opt[k][S]+opt[k][S+1]*(S+1)
此时时间复杂度为O(NM)
空间复杂度为O(NM)
问题得到了解决
可见对问题透彻的分析是得出最有效规划方式的前提。

很多时候一些状态是不需要的,或者某些维是可以合并的。
经过合理的分析我们可以抛弃一些冗余信息,减少状态,加速转移。