动态规划本来就很抽象，状态的设定和状态的转移都不好把握，而状态压缩的动态规划解决的就是那种状态很多，不容易用一般的方法表示的动态规划问题，这个就更加的难于把握了。难点在于以下几个方面：状态怎么压缩？压缩后怎么表示？怎么转移？是否具有最优子结构？是否满足后效性？涉及到一些位运算的操作，虽然比较抽象，但本质还是动态规划。找准动态规划几个方面的问题，深刻理解动态规划的原理，开动脑筋思考问题。这才是掌握动态规划的关键。
动态规划最关键的要处理的问题就是位运算的操作，容易出错，状态的设计也直接决定了程序的效率，或者代码长短。状态转移方程一定要仔细推敲，不可一带而过，要思考为什么这么做，掌握一个套路，遇见这类问题能快速的识别出问题的本质，找出状态转移方程和DP的边界条件。
下面是一些关于状态压缩DP的题目，大都不难。状压DP的东西还有很多，还会接着总结。
【题目大意】一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)
【解析】根据题意，把每一行的状态用二进制的数表示，0代表不在这块放牛，1表示在这一块放牛。首先很容易看到，每一行的状态要符合牧场的硬件条件，即牛必须放在能放牧的方格上。这样就能排除一些状态。另外，牛与牛之间不能相邻，这样就要求每一行中不能存在两个相邻的1，这样也能排除很多状态。然后就是根据上一行的状态转移到当前行的状态的问题了。必须符合不能有两个1在同一列（两只牛也不能竖着相邻）的条件。这样也能去掉一些状态。然后，上一行的所有符合条件的状态的总的方案数就是当前行该状态的方案数。
【状态表示】dp[state][i]：在状态为state时，到第i行符合条件的可以放牛的方案数
【状态转移方程】dp[state][i] = Sigma dp[state'][i-1] （state'为符合条件的所有状态）
【DP边界条件】首行放牛的方案数dp[state][1] = 1(state符合条件) OR 0 (state不符合条件)
Read full article from 动态规划（二）（状态压缩DP 一） - ACCRY
No comments:
Post a Comment