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

動態(tài)規(guī)劃的優(yōu)化動態(tài)規(guī)劃的時間優(yōu)化使用動態(tài)規(guī)劃方法解題，對于不少問題之所以具有較高的時間效率，關(guān)鍵在于它減少了“冗余”。所謂“冗余”，就是指不必要的計算或重復(fù)計算部分，算法的冗余程度是決定算法效率的關(guān)鍵。動態(tài)規(guī)劃在將問題規(guī)模不斷縮小的同時，記錄已經(jīng)求解過的子問題的解，充分利用求解結(jié)果，避免了反復(fù)求解同一子問題的現(xiàn)象，從而減少了冗余。時間復(fù)雜度=狀態(tài)總數(shù)*每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)*每次狀態(tài)轉(zhuǎn)移的時間四邊形不等式的優(yōu)化合并石子問題：在一個操場上擺放著一排n（n≤20）堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試編程求出將n堆石子合并成一堆的最小得分和最大得分以及相應(yīng)的合并方案。狀態(tài)表示為：m[i,j]，1≤i≤j≤n，表示合并d[i..j]所得到的最小得分，則狀態(tài)轉(zhuǎn)移方程和邊界條件為：m[i,j]=0i=ji＜j令s[i,j]=k，w[i,j]=當(dāng)函數(shù)w[i,j]滿足時，稱w滿足四邊形不等式。當(dāng)函數(shù)w[i,j]滿足w[i’,j]≤w[i,j’]時稱w關(guān)于區(qū)間包含關(guān)系單調(diào)令s[i,j]=max{k|m[i,j]=m[i,k-1]+m[k,j]+w[i,j]}由函數(shù)m[i,j]滿足四邊形不等式可以推出函數(shù)s[i,j]的單調(diào)性，即s[i,j]≤s[i,j+1]≤s[i+1,j+1],i≤j改正后的轉(zhuǎn)移方程程序?qū)崿F(xiàn)S[I,i]:=I;S[I,i+1]:=i+1/I;ForL:=3tondofori:=1tondo[j:=i+L-1;fork:=s[I,j-1]tos[i+1,j]doifm[I,j]<m[I,k-1]+m[k,j]+w[I,j]then[

更新m[I,j]s[I,j]:=k]]農(nóng)田個數(shù)你的老家在河北農(nóng)村。過年時，你回老家去拜年。你家有一片NM農(nóng)田，將其看成一個NM的方格矩陣，有些方格是一片水域。你的農(nóng)村伯伯聽說你是學(xué)計算機(jī)的，給你出了一道題：他問你：這片農(nóng)田總共包含了多少個不存在水域的正方形農(nóng)田。兩個正方形農(nóng)田不同必須至少包含下面的兩個條件中的一條：邊長不相等左上角的方格不是同一方格輸入輸入數(shù)據(jù)第一行為兩個由空格分開的正整數(shù)N、M（1<=m<n<=1000）

第2行到第N+1行每行有M個數(shù)字（0或1），描述了這一片農(nóng)田。0表示這個方格為水域，否則為農(nóng)田（注意：數(shù)字之間沒有空格，而且每行不會出現(xiàn)空格）輸出滿足條件的正方形農(nóng)田個數(shù)。樣例輸入33110110000樣例輸出5樣例說明邊長為1的正方形農(nóng)田有4塊邊長為2的正方形農(nóng)田有1塊合起來就是5塊分析

設(shè)F[I，J]表示以方格（I，J）為右下角，可以得到的最大無水正方形邊長，那么顯然如果（I，J）是水域，F(xiàn)[I，J]=0；否則F[I，J]=Min{F[I-1，J]，F(xiàn)[I，J-1]，F(xiàn)[I-1，J-1]}+1求出了F數(shù)組的值后，我們可以用F1[I]表示F數(shù)組中，值為I的個數(shù)。顯然，假定邊長為I的正方形數(shù)目為Sum[I]，那么有Sum[I]=Sum[I+1]+F1[I]最后只要算出Sum數(shù)組各個值的和為問題的解。通過分析上面的算法會發(fā)現(xiàn)，它的時間復(fù)雜度為O（N^2），采用滾動數(shù)組的話，空間復(fù)雜度為O（N），幾乎達(dá)到理論的下界了。

火車票

由于n最大可以為10000，如果要在規(guī)定時間內(nèi)出解，算法的時間復(fù)雜度必須嚴(yán)格控制在n^2以內(nèi)，這就使我們想到了動態(tài)規(guī)劃。設(shè)f[I]表示從起點(diǎn)站（站A）到站I的最少費(fèi)用。X表示某一站J與站I的間距離。F[I]=min{f[j]+cost(I,j)}(a<=j<I)c1(0<X<=L1)Cost(I,j)=c2(L1<X<=L2)c3(L2<X<=L3)∞(L3<X)邊界：f[a]=0該算法的空間復(fù)雜度為O(n)，時間復(fù)雜度為O(n^2)。當(dāng)n=10000時，程序的運(yùn)行速度就很慢了，很難在規(guī)定時間內(nèi)出解，看來優(yōu)化算法是必要的。首先我們要肯定一點(diǎn)，就是如果I<j，則F[I]<=F[J]。證明如下：假設(shè)F[J]是由F[K]推出來的。當(dāng)k<I時，由于I<j，那么從站K到站I的路程比從站K到站J的路程短，又由于從站K到站J可以買一張直達(dá)票（F[J]由F[K]推出），從站K到站I必然也可以買一張直達(dá)票，而該直達(dá)票的票價絕對不會超過從站K到站J的直達(dá)票的價格，所以先從站A到站K再到站I比先從站A到站K再到站J所需的費(fèi)用少或相等。而先從站A到站K，再到站I的費(fèi)用不一定是從站A到站I的最少費(fèi)用，但從假設(shè)知從站A到站K再到站J的費(fèi)用一定是從站A到站J的最少費(fèi)用，所以當(dāng)k<I時，F(xiàn)[I]<=F[J]。當(dāng)k=I時，由于F[J]等于F[I]加上一個不為0的數(shù)，所以此時F[I]<F[J]。當(dāng)k>I時，就將問題轉(zhuǎn)化為證F[I]<=F[K]，經(jīng)過若干次這樣的轉(zhuǎn)化后，必可以找到一個F[Jt]，它是由F[Kt]推出的，而Kt<=I，從前面的證明中可以證出此時的F[Jt]>=F[I],而F[Jt]<F[Jt-1]<f[Jt-2]<……F[J],所以此時F[I]<F[J]。證畢。有了上述結(jié)論后，不難想到，如果先從站A到站K，再買一張C1（或C2、C3）的票從站K到站I的總費(fèi)用為從站A到站I的最少費(fèi)用，那么站K為可以用一張C1（或C2、C3）的票直達(dá)站I的最遠(yuǎn)站。由此我們可以稍微改一下動態(tài)轉(zhuǎn)移方程：f[I]=min{f[k1]+c1,f[k2]+c2,f[k3]+c3}K1、K2、K3為大于等于A且能夠用一張C1、C2、C3的票直達(dá)站I的最遠(yuǎn)站號。現(xiàn)在的問題是該如何用一個高效的算法求出每一個I對應(yīng)的K1、K2、K3的值。最容易想到的方法是每次用一個從A到I的循環(huán)查找，但這么以來，整個算法的時間復(fù)雜度仍為O(n^2)。由于I-1號站比I號站更接近站A，所以站I-1對應(yīng)的K1、K2、K3的值肯定比站I對應(yīng)的K1、K2、K3的值小或相等。所以我們的求當(dāng)前的K1、K