0819动态规划之状态压缩.pptx

态规划的状态有时候比较恶心,不容易表示出来,需要用一些编码技术,把状态压缩的用简单的方式表示出来。 典型方式:当需要表示一个集合有哪些元素时,往往利用2进制用一个整数表示。 动态规划本来就很抽象,状态的设定和状态的转移都不好把握,而状态压缩的动态规划解决的就是那种状态很多,不容易用一般的方法表示的动态规划问题,这个就更加的难于把握了。难点在于以下几个方面:状态怎么压缩?压缩后怎么表示?怎么转移?是否具有最优子结构?是否满足后效性?涉及到一些位运算的操作,虽然比较抽象,但本质还是动态规划。找准动态规划几个方面的问题,深刻理解动态规划的原理,开动脑筋思考问题。这才是掌握动态规划的关键