动态规划2.ppt

括号序列
定义如下规则序列(字符串):
空序列是规则序列;
如果S是规则序列,那么(S)和[S]也是规则序列;
如果A和B都是规则序列,那么AB也是规则序列。
例如,下面的字符串都是规则序列:
(), [], (()), ([]), ()[], ()[()]
这几个则不是规则序列:
(, [, ], )(, ([()
现在,给出一些由‘(’,‘)’,‘[’,‘]’构成的序列,请添加尽量少的括号,得到一个规则序列。
分析
d[i,j]: 子串i…j最少需要添加的括号数
状态转移
S形如(S’)或者[S’]: d[i+1,j-1]
S形如(S’或者[S’: d[i+1,j]+1
S形如S’)或者S’]: d[i,j-1]+1
长度大于1: d[i,k]+d[k+1,j] (i<=k<=j-1)
状态O(n2), 转移O(n), 共(n3)
棋盘分割
将一个8×8的棋盘进行如图所示的分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n(n<15)块矩形棋盘(每次切割都只能沿着棋盘格子的边进行)。
棋盘分割
原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
分析
变形均方差公式
平均值是一定的(等于所有方格里的数的和除以n)
只需要让每个矩形总分的平方和尽量小
分析
考虑左上角坐标为(x1,y1),右下角坐标为(x2,y2)的棋盘,设它把切割k次以后得到的k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2]
状态转移: 沿着某横线切或者竖线切,然后选一块继续切, 如横着切的两类决策是
d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]
d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]
其中x1<=a<=x2
分析
状态d[k,x1,y1,x2,y2]
设m为棋盘边长,则状态数目为m4n,决策数目为O(m)
转移时间取决于计算s[x1,y1,x2,y2]的时间
预处理先用O(m2)时间算出左上角为(1,1)的所有矩阵元素和,这样状态转移时间就是O(1),总的时间复杂度为O(m5n)
决斗
编号为1~n的n个人按逆时针方向排成一圈,他们要决斗n-1场。每场比赛在某相邻两人间进行,败者退出圈子,紧靠败者右边的人成为与胜者直接相邻的人。
任意两人之间决斗的胜负都将在一矩阵中给出(如果A[i,j]=1则i与j决斗i总是赢,如果A[i,j]=0则i与j决斗时i总是输),
求出所有可能赢得整场决斗的人的序号
分析
f[i,j]表示是否有可能i和j相遇, 则第i个人能取得最后的胜利当且仅当f[i,i]为true
状态转移: 考虑相遇前的最后一步, 则f[I,j]为true当且仅当
能找到一个k, 使得i能遇k, k能遇到j, 且
i或者j能打败k
状态有O(n2)个, 转移有O(n)个, 共O(n3)
F[I,j]=(f[I,k] and f[k,j]) and (A[I,k] or A[j,k]),i<k<j