动态规划经典教程——多维状态和动态规划的优化

3.多维状态和动态规划的优化

一般多维动态规划的时，空间复杂度较高，所以我们要想办法将其优化，我就把多维动态规划和动态规划的优化放到一起了……

多维动态规划以三，四维最为常见，在多的也没有太大的研究价值，其实多维动态规划大多也就是上面的一维，和二维的加一些条件，或是在多进程动态规划中要用到。当然除了这些特点外，状态的表示也有一些共性。

三维：状态opt[i,j,k]一般可表示下面的含义：

（1）二维状态的基础上加了某个条件，或其中一维变成两个。

比如opt[L,i]表示起点为I，长度为L的序列的最优值。opt[L,i,j]就可表示起点是i和起点是j，长度是L的两个序列的最优值。

（2）I，J，K组合表示一个正方形（（i,j）点为一角，边长为K）。

（3）I，J，K组合表示一个等边三角形（（i,j）点为一角，边长为K）。

四维：除了二维和三维加条件外，还可以用i,j,k,t组合来描述一个矩形，

（i,j）点和（k,t）点是两个对顶点。

四维以上的一般都是前几维加了条件了，这里就不多说了。

动态规划的优化：

动态规划的优化往往需要较强的数学功底。

常见空间优化：

滚动数组，滚动数组在前面也提到过，其实很简单，如果一个状态的决策的步长为N就只保留以求出的最后N（一般N=1）个阶段的状态，因为当前状态只和后N个阶段中的状态有关，再以前的已经利用过了，没用了就可以替换掉了。具体实现是最好只让下标滚动（这样更省时间）。

X：=K1，K1：=K2，K2；=K3，K3：=X这样就实现了一个N=3的下标的滚动，在滚动完如果状态是涉及累加，累乘类的操作要注意将当前要求的状态初始化。

常见时间优化：利用一些数据结构（堆，并查集，HASH）降低查找复杂度。

时间空间双重优化：改变状态的表示法，降低状态维数。

具体的多维动态规划和动态规划的优化，我们从题目里体会吧！

3.1矩阵问题

先看一道题

例题27   盖房子   来源：VIJOS P1057

【问题描述】

永恒の灵魂最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所房子，这个房子必须是正方形的。
但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。
    他希望找到一块最大的正方形无瑕疵土地来盖房子。
    不过，这并不是什么难题，永恒の灵魂在10分钟内就轻松解决了这个问题。现在，您也来试试吧。

【输入文件】

输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。

【输出文件】

一个整数，最大正方形的边长。

【输入样例】

4 4

0 1 1 1

1 1 1 0

0 1 1 0

1 1 0 1

【输出样例】

2

【问题分析】

题目中说要求一个最大的符合条件的正方形，所以就想到判断所有的正方形是否合法。

这个题目直观的状态表示法是opt[i,j,k]基类型是boolean，判断以（i,j）点为左上角（其实任意一个角都可以，依据个人习惯）,长度为K的正方形是否合理，再找到一个K值最大的合法状态就可以了（用true表示合理，false表示不合理）。其实这就是递推，（决策唯一）。

递推式：

opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1)

时间复杂度：

状态数O（N3）*转移代价O（1）=总复杂度O（N3）

空间复杂度：

O（N3）

由于空间复杂度和时间复杂度都太高，不能AC，我们就的再想想怎么优化？

显然何以用滚动数组优化空间，但是时间复杂度仍然是O（N3）。这就需要我们找另外一种简单的状态表示法来解了。

仔细分析这个题目，其实我们没必要知道正方形的所有长度，只要知道以一个点为左上角的正方形的最大合理长度就可以了。

如果这个左上角是0那么它的最大合理长度自然就是0（不可能合理）。

如果这个左上角是1呢？

回顾上面的递推式，我们考虑的是以它的右面，下面，右下这个三个方向的正方形是否合理，所以我们还是要考虑这三个方向。具体怎么考虑呢？

如果这三个方向合理的最大边长中一个最小的是X，那么它的最大合理边长就是X+1。为什么呢？

看个例子：

0 1 1 1 1 1

1 1 1 1 1 1

0 1 0 1 1 0

1 1 0 1 1 1

上例中红色的正方形，以（1,3）点为左上角，以（1，4），（2，3），（2，4）这三个点的最大合理边长分别是2，1，2。其中最小的是以（2，3）为左上角的正方形，最大合理边长是1。因为三个方向的最大合理边长大于等于1，所以三个方向上边长为1的正方形是合理的，即上面低推式中:

opt[1,3,2]=opt[1,4,1] and opt[2,3,1] and opt[2,4,1] and (a[1,3]=1) = true 成立

这样就把一个低推判定性问题转化成最优化问题从而节省空间和时间。

具体实现：

设计一个状态opt[i,j]表示以（i,j）为左上角的正方形的最大合理边长。

状态转移方程：

min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1       (a[i,j]=1)

opt[i,j]=0                                                          (a[i,j]=0)

时间复杂度：状态数O（N2）*转移代价O（1）=总代价O（N2）

空间复杂度：O（N2）

【源代码】

program P1057;

const

maxn=1010;

var

opt,a:array[0..maxn,0..maxn] of longint;

n,m,ans:longint;

procedure init;

var

i,j:longint;

begin

read(n,m);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

end;

procedure main;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

for i:=n downto 1 do

for j:=m downto 1 do

if a[i,j]<>0 then

begin

opt[i,j]:=opt[i+1,j];

if opt[i,j+1]<opt[i,j] then

opt[i,j]:=opt[i,j+1];

if opt[i+1,j+1]<opt[i,j] then

opt[i,j]:=opt[i+1,j+1];

inc(opt[i,j]);

end;

ans:=0;

for i:=1 to n do

for j:=1 to m do

if opt[i,j]>ans then ans:=opt[i,j];

writeln(ans);

end;

begin

init;

main;

end.