動態(tài)規(guī)劃經(jīng)典教程——多維狀態(tài)和動態(tài)規(guī)劃的優(yōu)化

3.多維狀態(tài)和動態(tài)規(guī)劃的優(yōu)化

一般多維動態(tài)規(guī)劃的時，空間復(fù)雜度較高，所以我們要想辦法將其優(yōu)化，我就把多維動態(tài)規(guī)劃和動態(tài)規(guī)劃的優(yōu)化放到一起了……

多維動態(tài)規(guī)劃以三，四維最為常見，在多的也沒有太大的研究價值，其實多維動態(tài)規(guī)劃大多也就是上面的一維，和二維的加一些條件，或是在多進(jìn)程動態(tài)規(guī)劃中要用到。當(dāng)然除了這些特點外，狀態(tài)的表示也有一些共性。

三維：狀態(tài)opt[i,j,k]一般可表示下面的含義：

（1）二維狀態(tài)的基礎(chǔ)上加了某個條件，或其中一維變成兩個。

比如opt[L,i]表示起點為I，長度為L的序列的最優(yōu)值。opt[L,i,j]就可表示起點是i和起點是j，長度是L的兩個序列的最優(yōu)值。

（2）I，J，K組合表示一個正方形（（i,j）點為一角，邊長為K）。

（3）I，J，K組合表示一個等邊三角形（（i,j）點為一角，邊長為K）。

四維：除了二維和三維加條件外，還可以用i,j,k,t組合來描述一個矩形，

（i,j）點和（k,t）點是兩個對頂點。

四維以上的一般都是前幾維加了條件了，這里就不多說了。

動態(tài)規(guī)劃的優(yōu)化：

動態(tài)規(guī)劃的優(yōu)化往往需要較強(qiáng)的數(shù)學(xué)功底。

常見空間優(yōu)化：

滾動數(shù)組，滾動數(shù)組在前面也提到過，其實很簡單，如果一個狀態(tài)的決策的步長為N就只保留以求出的最后N（一般N=1）個階段的狀態(tài)，因為當(dāng)前狀態(tài)只和后N個階段中的狀態(tài)有關(guān)，再以前的已經(jīng)利用過了，沒用了就可以替換掉了。具體實現(xiàn)是最好只讓下標(biāo)滾動（這樣更省時間）。

X：=K1，K1：=K2，K2；=K3，K3：=X這樣就實現(xiàn)了一個N=3的下標(biāo)的滾動，在滾動完如果狀態(tài)是涉及累加，累乘類的操作要注意將當(dāng)前要求的狀態(tài)初始化。

常見時間優(yōu)化：利用一些數(shù)據(jù)結(jié)構(gòu)（堆，并查集，HASH）降低查找復(fù)雜度。

時間空間雙重優(yōu)化：改變狀態(tài)的表示法，降低狀態(tài)維數(shù)。

具體的多維動態(tài)規(guī)劃和動態(tài)規(guī)劃的優(yōu)化，我們從題目里體會吧！

3.1矩陣問題

先看一道題

例題27   蓋房子   來源：VIJOS P1057

【問題描述】

永恒の靈魂最近得到了面積為n*m的一大塊土地（高興ING^_^），他想在這塊土地上建造一所房子，這個房子必須是正方形的。
但是，這塊土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。這些瑕疵十分惡心，以至于根本不能在上面蓋一磚一瓦。
    他希望找到一塊最大的正方形無瑕疵土地來蓋房子。
    不過，這并不是什么難題，永恒の靈魂在10分鐘內(nèi)就輕松解決了這個問題?，F(xiàn)在，您也來試試吧。

【輸入文件】

輸入文件第一行為兩個整數(shù)n,m（1<=n,m<=1000），接下來n行，每行m個數(shù)字，用空格隔開。0表示該塊土地有瑕疵，1表示該塊土地完好。

【輸出文件】

一個整數(shù)，最大正方形的邊長。

【輸入樣例】

4 4

0 1 1 1

1 1 1 0

0 1 1 0

1 1 0 1

【輸出樣例】

2

【問題分析】

題目中說要求一個最大的符合條件的正方形，所以就想到判斷所有的正方形是否合法。

這個題目直觀的狀態(tài)表示法是opt[i,j,k]基類型是boolean，判斷以（i,j）點為左上角（其實任意一個角都可以，依據(jù)個人習(xí)慣）,長度為K的正方形是否合理，再找到一個K值最大的合法狀態(tài)就可以了（用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)

時間復(fù)雜度：

狀態(tài)數(shù)O（N3）*轉(zhuǎn)移代價O（1）=總復(fù)雜度O（N3）

空間復(fù)雜度：

O（N3）

由于空間復(fù)雜度和時間復(fù)雜度都太高，不能AC，我們就的再想想怎么優(yōu)化？

顯然何以用滾動數(shù)組優(yōu)化空間，但是時間復(fù)雜度仍然是O（N3）。這就需要我們找另外一種簡單的狀態(tài)表示法來解了。

仔細(xì)分析這個題目，其實我們沒必要知道正方形的所有長度，只要知道以一個點為左上角的正方形的最大合理長度就可以了。

如果這個左上角是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 成立

這樣就把一個低推判定性問題轉(zhuǎn)化成最優(yōu)化問題從而節(jié)省空間和時間。

具體實現(xiàn)：

設(shè)計一個狀態(tài)opt[i,j]表示以（i,j）為左上角的正方形的最大合理邊長。

狀態(tài)轉(zhuǎn)移方程：

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)

時間復(fù)雜度：狀態(tài)數(shù)O（N2）*轉(zhuǎn)移代價O（1）=總代價O（N2）

空間復(fù)雜度：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.