轉載自:教你徹底學會動态規劃——入門篇
1、概述
動态規劃相信大家都知道,動态規劃算法也是新手在剛接觸算法設計時很苦惱的問題,有時候覺得難以了解,但是真正了解之後,就會覺得動态規劃其實并沒有想象中那麼難。網上也有很多關于講解動态規劃的文章,大多都是叙述概念,講解原理,讓人覺得晦澀難懂,即使一時間看懂了,發現當自己做題的時候又會覺得無所适從。我覺得,了解算法最重要的還是在于練習,隻有通過自己練習,才可以更快地提升。話不多說,接下來,下面我就通過一個例子來一步一步講解動态規劃是怎樣使用的,隻有知道怎樣使用,才能更好地了解,而不是一味地對概念和原理進行反複琢磨。
2、例題解析
首先,我們看一下這道題(此題目來源于北大POJ):數字三角形(POJ1163)
在上面的數字三角形中尋找一條從頂部到底邊的路徑,使得路徑上所經過的數字之和最大。路徑上的每一步都隻能往左下或 右下走。隻需要求出這個最大和即可,不必給出具體路徑。 三角形的行數大于1小于等于100,數字為 0 - 99
輸入格式:
5 //表示三角形的行數 接下來輸入三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
2.1 解題思路
要求:輸出最大和
接下來,我們來分析一下解題思路:
首先,肯定得用二維數組來存放數字三角形
然後我們用D( r, j) 來表示第r行第 j 個數字(r,j從1開始算)
我們用MaxSum(r, j)表示從D(r,j)到底邊的各條路徑中,最佳路徑的數字之和。
是以,此題的最終問題就變成了求 MaxSum(1,1)
2.2 遞歸算法
當我們看到這個題目的時候,首先想到的就是可以用簡單的遞歸來解題:
D(r, j)出發,下一步隻能走D(r+1,j)或者D(r+1, j+1)。故對于N行的三角形,我們可以寫出如下的遞歸式:
if ( r == N)
MaxSum(r,j) = D(r,j)
else
MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)
複制
根據上面這個簡單的遞歸式,我們就可以很輕松地寫出完整的遞歸代碼:
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
int D[MAX][MAX];
int n;
int MaxSum(int i, int j){
if(i==n)
return D[i][j];
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
return max(x,y)+D[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
cout << MaxSum(1,1) << endl;
}
複制
對于如上這段遞歸的代碼,當我送出到POJ時,會顯示如下結果:
對的,代碼運作逾時了,為什麼會逾時呢?
答案很簡單,因為我們重複計算了,當我們在進行遞歸時,計算機幫我們計算的過程如下圖:
就拿第三行數字1來說,當我們計算從第2行的數字3開始的MaxSum時會計算出從1開始的MaxSum,當我們計算從第二行的數字8開始的MaxSum的時候又會計算一次從1開始的MaxSum,也就是說有重複計算。這樣就浪費了大量的時間。也就是說如果采用遞規的方法,深度周遊每條路徑,存在大量重複計算。則時間複雜度為 2的n次方,對于 n = 100 行,肯定逾時。
接下來,我們就要考慮如何進行改進,我們自然而然就可以想到如果每算出一個MaxSum(r,j)就儲存起來,下次用到其值的時候直接取用,則可免去重複計算。那麼可以用n方的時間複雜度完成計算。因為三角形的數字總數是 n(n+1)/2
2.3 遞歸轉動态規劃
根據這個思路,我們就可以将上面的代碼進行改進,使之成為記憶遞歸型的動态規劃程式:
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int MaxSum(int i, int j){
if( maxSum[i][j] != -1 )
return maxSum[i][j];
if(i==n)
maxSum[i][j] = D[i][j];
else{
int x = MaxSum(i+1,j);
int y = MaxSum(i+1,j+1);
maxSum[i][j] = max(x,y)+ D[i][j];
}
return maxSum[i][j];
}
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++) {
cin >> D[i][j];
maxSum[i][j] = -1;
}
cout << MaxSum(1,1) << endl;
}
複制
當我們送出如上代碼時,結果就是一次AC
雖然在短時間内就AC了。但是,我們并不能滿足于這樣的代碼,因為遞歸總是需要使用大量堆棧上的空間,很容易造成棧溢出,我們現在就要考慮如何把遞歸轉換為遞推,讓我們一步一步來完成這個過程。
我們首先需要計算的是最後一行,是以可以把最後一行直接寫出,如下圖:
現在開始分析倒數第二行的每一個數,現分析數字2,2可以和最後一行4相加,也可以和最後一行的5相加,但是很顯然和5相加要更大一點,結果為7,我們此時就可以将7儲存起來,然後分析數字7,7可以和最後一行的5相加,也可以和最後一行的2相加,很顯然和5相加更大,結果為12,是以我們将12儲存起來。以此類推。。我們可以得到下面這張圖:
然後按同樣的道理分析倒數第三行和倒數第四行,最後分析第一行,我們可以依次得到如下結果:
上面的推導過程相信大家不難了解,了解之後我們就可以寫出如下的遞推型動态規劃程式:
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
for( int i = 1;i <= n; ++ i )
maxSum[n][i] = D[n][i];
for( int i = n-1; i>= 1; --i )
for( int j = 1; j <= i; ++j )
maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];
cout << maxSum[1][1] << endl;
}
複制
我們的代碼僅僅是這樣就夠了嗎?當然不是,我們仍然可以繼續優化,而這個優化當然是對于空間進行優化,其實完全沒必要用二維maxSum數組存儲每一個MaxSum(r,j),隻要從底層一行行向上遞推,那麼隻要一維數組maxSum[100]即可,即隻要存儲一行的MaxSum值就可以。
對于空間優化後的具體遞推過程如下:
接下裡的步驟就按上圖的過程一步一步推導就可以了。進一步考慮,我們甚至可以連maxSum數組都可以不要,直接用D的第n行直接替代maxSum即可。但是這裡需要強調的是:雖然節省空間,但是時間複雜度還是不變的。
依照上面的方式,我們可以寫出如下代碼:
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int * maxSum;
int main(){
int i,j;
cin >> n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin >> D[i][j];
maxSum = D[n]; //maxSum指向第n行
for( int i = n-1; i>= 1; --i )
for( int j = 1; j <= i; ++j )
maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];
cout << maxSum[1] << endl;
}
複制
3、總結
3.1 遞歸到動規的一般轉化方法
遞歸函數有n個參數,就定義一個n維的數組,數組的下标是遞歸函數參數的取值範圍,數組元素的值是遞歸函數的傳回值,這樣就可以從邊界值開始, 逐漸填充數組,相當于計算遞歸函數值的逆過程。
3.2 動規解題的一般思路
1. 将原問題分解為子問題
- 把原問題分解為若幹個子問題,子問題和原問題形式相同或類似,隻不過規模變小了。子問題都解決,原問題即解決(數字三角形例)。
- 子問題的解一旦求出就會被儲存,是以每個子問題隻需求 解一次。
2.确定狀态
- 在用動态規劃解題時,我們往往将和子問題相關的各個變量的一組取值,稱之為一個“狀 态”。一個“狀态”對應于一個或多個子問題, 所謂某個“狀态”下的“值”,就是這個“狀 态”所對應的子問題的解。
- 所有“狀态”的集合,構成問題的“狀态空間”。“狀态空間”的大小,與用動态規劃解決問題的時間複雜度直接相關。 在數字三角形的例子裡,一共有N×(N+1)/2個數字,是以這個問題的狀态空間裡一共就有N×(N+1)/2個狀态。
整個問題的時間複雜度是狀态數目乘以計算每個狀态所需時間。在數字三角形裡每個“狀态”隻需要經過一次,且在每個狀态上作計算所花的時間都是和N無關的常數。
3.确定一些初始狀态(邊界狀态)的值
以“數字三角形”為例,初始狀态就是底邊數字,值就是底邊數字值。
4. 确定狀态轉移方程
定義出什麼是“狀态”,以及在該“狀态”下的“值”後,就要找出不同的狀态之間如何遷移――即如何從一個或多個“值”已知的 “狀态”,求出另一個“狀态”的“值”(遞推型)。狀态的遷移可以用遞推公式表示,此遞推公式也可被稱作“狀态轉移方程”。
數字三角形的狀态轉移方程:
3.3 能用動規解決的問題的特點
1) 問題具有最優子結構性質。如果問題的最優解所包含的 子問題的解也是最優的,我們就稱該問題具有最優子結 構性質。
2) 無後效性。目前的若幹個狀态值一旦确定,則此後過程的演變就隻和這若幹個狀态的值有關,和之前是采取哪種手段或經過哪條路徑演變到目前的這若幹個狀态,沒有關系。