动态规划2

• 下面就是由某个二进制数能转化到另一个二进制数的问 题了。如下图,状态由100100 111100 和110100 ：
动态规划
• 显然，对于每一行,宽度为w,每格可放0和1，因此 有2w 种状态，如下图：
• 设f(i,s)表示铺到第i行，前i-1行全部铺满，状态为s 的方案数，则
f (i, s) f (i 1,s' ),其中s'的状态能变到 s
(])[()(])] 0123456789
(1,9)=6
dfs(0,9)=8
(1,1)+(3,9) +2=8
(1,4)+(6,9) +2=4
(1,7)+(9,9) +2=6
(2,9)=6 (...) (3,9)=6
(4,8)+(10,9) +2=6 (4,6)+(8,9) +2=4
(...)
(.)
每个节点只会算一次，这就是 记忆化的好处，图中 说明了这点
(6,8)=0
(4,5)=2
(...)=0
状态压缩
基本位操作（ & | ^ ~ >> << ） 若当前状态为s,对s 有下列操作： 1.判断第i位是否为0 (s&(1<< i)) == 0，意思是将1左 移i位与s进行与运算后，看结果是否为0. 判断第i位是否为1同理。 2.将第i位置1 s|(1<<i),意思是将1左移动i位与s进行或 运算. 3.将第i位置0 s&~(1<<i),意思是s与第i位为0，其余位 为1的数进行与运算。 例如：s=1010101，i=5 (s&1<<i): 1010101 & 0100000 = 0 s|(1<<i): 1010101 | 0100000 = 1110101 s&~(1<<i): 1010101 & 1011111 = 1010101
思考一下该 怎么做？
ans:7
搜索的方法，每个点出发往下搜，一直搜到不能划为止，貌似 问题就解决了，但是呢？复杂度太大，O(n^2*m^2)的复杂度。 动态规划的方法，首先想个状态，dp[i][j]表示到达(i,j)这个点还 能划多远，向四个方向转移，状态确实蛮好的，可是转移就有一 点困难了。 于是想到记忆化搜索，状态不变，用递归来转移。
想一想，怎么做?
寻找状态：dp[i][j]为i~j的最大括号数。 根据什么来转移呢？
考虑第i个括号，有两种情况： 1.i无效，直接算dp[i + 1][j]; 2.找到和i匹配的右括号k，分两边算并加起来。 dp[i][j] = dp[i+1][k-1] + 2 + dp[k + 1][j] 循环不是很好处理（当然也是可以的），于是可以 考虑用递归来实现，即记忆化搜索。
进一步分析
• 性质1：如果w和h都是奇数，则无解，否则有解。 证明：w,h都是奇数，则w*h也是奇数，由于1×2 的砖有2块，因此无论铺多少块都是偶数，因此不 能覆盖所有的地板。如果地板的面积S是偶数，肯 定能被2整除，因此可以用S/2块砖铺满整个地板。 • 性质2：对于每铺一次地板，只会影响所铺的上下 两行。 证明：因为是1×2的砖铺，性质显然。 • 性质3：如果按行铺地板，每一行的铺法都类似。 证明：显然！
问题二：括号匹配问题(poj 2955) 问题描述：
给你一串由'('、')'、'['、']'组成的字符串，问子序列中 最长的合法括号串有多长。合法指括号都两两配对，子串中 不能出现交叉、多余的括号。
样例： ((())) ()()() ([]]) )[)( ([][][) 输出： 6 6 4 0 6
W=4，h=2的求解过程
核心代码： void dfs(int row,int s1,int col,int s2) // 行 当前行状态 列 下一行状态 { if(col==m) // 如果当前行铺满 { dp[row+1][s2]+=dp[row][s1]; // 转移到下一行 return ; } if(s1&(1<<col)) dfs(row,s1,col+1,s2); // 当前行col这点已经铺过了， 不能在这里铺，则下一行的这个点肯定为0，1->0 else // 当前行col这点还没有铺过 { dfs(row,s1,col+1,s2|(1<<col)); // 竖着放方块 0->1 if(col+1<m&&(s1&(1<<col+1))==0) dfs(row,s1,col+2,s2); // col+1这点也没有铺，可以横着放方块 00->00 } }
欢迎加入我们的暑假集训队 这里是一个很能锻炼人的地方！
人一我百，人十我万！追逐青春的梦想，怀着自信 的心，永不放弃！ --by kuangbin
动态规划的方程： dp[i][j]=max(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+1; (i，j)比其他点高 现在的方程： dp[i][j]=max(dfs(i-1,j),dfs(i+1,j),dfs(i,j-1),dfs(i,j+1))+1; (i，j)比其他点高 如何实现记忆化： 如果dp[i][j]已经算过了，就不用再算了，直接返回就够了。
一个示例
• 一个6×9的面积铺法如下图:
• 可以看出，在按行铺的过程中，某些砖会分成两 半，如图2，但最多也是向下突出一格，在图3中， 我们将图2的空隙填满，则又转移到了下一种状 态。
状态的表示
• 如果我们把行进行动态规划，则第i行的各种情况即表示 第i个阶段的的各种状态。 • 若某格被铺了砖，则用1表示，没有铺砖，则用0表示， 那么行的状态就是一个w个格子的0,1串，即w位的二进制 数。如下图状态为：100100
两种方法能否相互结合，解决各自的 不足呢？
于是记忆化搜索就这样诞生了，记忆化搜索=搜索的形式+动态规划的思想， 采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起， 扬长避短，简单实用，在信息学中有着重要的作用。
记忆化搜索！
来看一道题目（poj 1088 滑雪）
问题描述： 一个滑雪场（二维数组，每个点代表滑点的高度），一个人 可以从某个点滑向上下左右相邻四个点之一，当且仅当高度 减小，可从任意点出发，问一次最多能划多远。 样例： 34 8 8 21 23 5 9 19 6 6431
缺点：搜索树很大，结点数量非常多，结点之间的关系也非常复杂， 这是导致搜索算法效率低下的重要原因。有的情况下，状态的总数 并没有多少，有可能很多结点表示的都是同一个状态，我们把这样 的状态叫做“重叠子问题”。能否用一种办法来解决这个问题，以 避免重复地处理重叠子问题呢？
2.动态规划
具有子问题、最优子结构、子问题重叠、子问题独立 等特点（见上次ppt），比较高效。 动态规划能对于每个子问题只会算一次，不会产生“重叠子 问题”计算多次的情况，一般用循环来实现。 缺点是母问题的解决需要依赖于子问题，当母问题和子问题 的顺序（拓扑关系）不是很确定时，用循环就有点为难了。
• 初始值f(1,0)=1 • Ans=f[h+1][0] • 时间复杂度为O(h*2W)
放置操作
• 对于每一行有w个位置，所以每一行都有0～2w-1种状态。 • 对于当前行的状态s，它是由前一行的状态s’转化过来的， 显然，对于该行某个位置j： – 如果前一行该位置为0,那么该位置可以竖放 即 0-> 1 – 如果前一行连续两个位置为0,那么这两个连续位置可以 横放 即00-> 00 – 如果前一行该位置为1,显然该位置不能再放,于是应该把 该位置设置为0 ，即1-> 0
记忆化搜索与状态压缩
本人动态规划整理贴：ACM动态规划总结 本周周练：动态规划2
（记得顶哦）
To be what you want to be! --by utobe67
回顾一下搜索(dfs)和动态规划特点
1.搜索
搜索树： 一道搜索题目拿到手，我们往往要弄清楚这样一些问题：以什么作为状态？ 这些状态之间又有什么样的关系？其实，在这样的思考过程中，我们已经不 知不觉地将一个具体的问题抽象成了一个模型——树。 状态对应着顶点，状态之间的关系（或者说 从一个状态到另一个状态的形成过程）对应 着边。这样的一棵树就叫做搜索树。初始状 态对应着根结点，目标状态对应着目标结点。 我们的任务就是找到一条从根结点到目标结 点的路径——一个成功的解。
问题三：广场铺砖问题(poj 2411)
问题描述：
给出一个W行H列的广场，用1*2小砖铺盖，小砖之间互相不 能重叠，问有多少种不同的铺法？(广场最大为11*11) 输入 2 4 输出 5
如果情况能复杂一点呢？
分析
• 该题给出的广场的面积很小，给出了一种1*2的砖，问用砖 去铺广场有多少种铺法？ • 因为w,h<=11,很容易想到采用搜索的方法，可以采用深搜或 宽搜均可。 • 尽管w,h<=11，不很大，但是用1*2的砖铺，深度最大可达 到11，这样，如果采用深搜，对于每一层都需要回溯，时 间复杂度也很高。 • 如果采用宽搜，每一个点都有2种铺法，因此可以扩展出2 个结点，要求所有的解，必须扩展全部树结构，如果11层 结点，是个完全二叉树，结点数量可达211*11 =2121 ，无论空 间和时间都难以承受。 • 因此我们需要采用其他方法。