動態規劃合集——動態規劃基本原理
- 動態規劃原理
- 1258：【例9.2】數字金字塔 動態規劃原理
- 深度優先搜索
- 記憶化搜索
- 動態規劃（順推）
- 動態規劃原理
- 題解分析
- 滾動數組優化
- 動態規劃（逆推）
動態規劃原理
從數塔問題出發理解動態規劃。
1258：【例9.2】數字金字塔 動態規劃原理
1258：【例9.2】數字金字塔
深度優先搜索
問題要求的是從最高點按照規則走到最低點的路徑的最大的權值和，路徑起點終點固定，走法規則明確，可以考慮用搜索來解決。
定義遞歸函數void Dfs(int x,int y,int Curr)，其中(x,y)表示當前已從(1,1)走到(x,y)，目前已走路徑上的權值和為Curr。同時用另一個變量Ans記錄最大值。
當x=N時，到達遞歸出口，如果Curr比Ans大，則把Ans更新為Curr；
否則向下一行兩個位置行走，即遞歸執行
Dfs(x+1,y,Curr+A[x+1][y])和Dfs(x+1,y+1,Curr+A[x+1][y+1])。
該方法實際上是把所有路徑都走了一遍，由于每一條路徑都是由N-1步組成，每一步有“左”、“右”兩種選擇，因此路徑總數為 2 N ? 1 2^{N-1} 2N?1，
所以該方法的時間復雜度為 O ( 2 N ? 1 ) O(2^{N-1}) O(2N?1)，鐵定超時。
#include <iostream>
using namespace std;
int A[1005][1005], F[1005][1005], N, Ans;
void Dfs(int x, int y, int Curr) {if (x == N) {if (Curr > Ans)Ans = Curr;return;}//深度優先搜索是枚舉所有情況，這里只有兩個，而且用形參表示狀態，回溯無難度Dfs(x + 1, y, Curr + A[x + 1][y]);Dfs(x + 1, y + 1, Curr + A[x + 1][y + 1]);
}
int main() {cin >> N;for (int i = 1; i <= N; i++)for (int j = 1; j <= i; j++)cin >> A[i][j];Ans = 0;Dfs(1, 1, A[1][1]);cout << Ans << endl;return 0;
}
記憶化搜索
為了避免重復搜索，我們在dfs的基礎上開設全局數組F[x][y]記錄從(x,y)出發到終點路徑的最大權值和，一開始全部初始化為-1表示未被計算過。
在計算Dfs(x,y)時，首先查詢F[x][y]，如果F[x][y]不等于-1，說明Dfs(x,y)之前已經被計算過，直接返回 F[x][y]即可，否則計算出Dfs(x,y)的值并存儲在F[x][y]中。
由于F[x][y]對于每個合法的(x,y)都只計算過一次，
而且計算是在 O ( 1 ) O(1) O(1)內完成的，因此時間復雜度為 O ( N 2 ) O(N^2) O(N2)。可以通過本題。
記憶化搜索的本質已經是動態規劃。因為記憶化搜索也是記錄走過的分支，相當于已經解決了子問題，再遍歷這條路徑時直接由子問題解決當前問題即可。
#include <iostream>
#include <algorithm>
using namespace std;
int A[505][505],
F[505][505],N;
int Dfs(int x,int y) {if (F[x][y]== -1) {if (x==N)F[x][y]=A[x][y];elseF[x][y]=A[x][y]+max(Dfs(x+1,y),Dfs(x+1,y+1));}return F[x][y];
}
int main() {cin >> N;for(int i = 1;i <= N;i ++)for(int j = 1;j <= i;j ++)cin >> A[i][j];for(int i = 1;i <= N;i ++)for(int j = 1;j <= i;j ++)F[i][j] = -1;Dfs(1,1);cout << F[1][1] << endl;return 0;
}
動態規劃（順推）
動態規劃原理
動態規劃（Dynamic Programming，簡稱dp）是1951年美國數學家R.Bellman等人提出。具體詳見動態規劃_百度百科。
簡單總結就是：
-
一個大問題拆分成若干子問題，每個子問題的結果都是一個狀態。
-
由一個子問題解決另一個子問題選擇的方法稱為決策，在現實解決問題時我們都希望找到最優解，也就是最優決策。
-
同一個大問題拆分成的子問題之間往往都有一樣的規律。或者說，同一個大問題產生的任意兩個不同狀態之間有相同的聯系。這個聯系一般用數學公式表達，這個公式的專業術語叫狀態轉移方程。
-
動態規劃滿足兩個條件：
- 最優化原理：每一步決策都是最好的解決方案，都是從很多方案中選擇最好的方案。
- 無后效性：每個狀態除了第一個，都只由前階段的狀態和決策決定，和后續無關。
題解分析
1、狀態定義：
題目要求從(1,1)出發到最底層路徑最大權值和，路徑中是各個點串聯而成，路徑起點固定，終點和中間點相對不固定。因此定義F[x][y]表示從(1,1)出發到達(x,y)的路徑最大權值和。
最終答案Ans=max{F[N][1],F[N][2],...,F[N][N]}。
2、狀態轉移方程&邊界條件（或初始化方式）：
不去考慮(1,1)到(x,y)的每一步是如何走的，只考慮最后一步是如何走，根據最后一步是向
左還是向右分成以下兩種情況：
向左：最后一步是從(x-1,y)走到(x,y), 此類路徑被分割成兩部分，
第一部分是從
(1,1)走到(x-1,y)，第二部分是從(x-1,y)走到(x,y)，第一部分的最大權值和，此部分問題的性質與
F[x][y]的定義一樣，就是F[x-1][y]，第二部分就是
A[x][y]，兩部分相加即得到此類路徑的最大權值和為F[x-1,y]+A[x,y]；
向右： 最后一步是從(x-1,y-1)走到(x,y),此類路徑被分割成兩部分，
第一部分是從
(1,1)走到(x-1,y-1)，第二部分是從(x-1,y-1)走到(x,y)，分析方法如上。此類路徑的最大權值和為
F[x-1,y-1]+A[x,y]；
F[x][y]的計算需要求出上面兩種情況的最大值。綜上，得到狀態轉移方程如下：
F[x][y]=max{F[x-1,y-1],F[x-1][y]}+A[x,y]與遞歸關系式還需要遞歸終止條件一樣，這里我們需要對邊界進行處理以防止無休止地進行下去。觀察發現計算
F[x][y]時需要用到F[x-1][y-1]和F[x-1][y]，是上一行的元素，隨著遞歸的深入，
最終都要用到第一行的元素F[1][1],F[1][1]的計算不能再使用狀態轉移方程來求，而是應該直接賦予一個特值A[1][1]。這就是邊界條件。
綜上得：
狀態轉移方程：F[x][y]=max{F[x-1][y-1],F[x-1][y]}+A[x,y]
邊界條件：F[1][1]=A[1][1]
分析該動態規劃的正確性，分析該解法是否滿足使用動態規劃的兩個前提。
最優化原理：這個在分析狀態轉移方程時已經分析得比較透徹，明顯是符合最優化原理的。
無后效性：狀態轉移方程中，我們只關心
F[x-1][y-1]與F[x-1][y]的值，計算F[x-1][y-1]時可能有多種不同的決策對應著最優值，選哪種決策對計算F[x][y]的決策沒有影響，
F[x-1][y]也是一樣。這就是無后效性。在以后的題目中可能不會提及，但處處都充斥著這兩個前提的分析。
3、填表（或程序實現）：
由于狀態轉移方程就是遞歸關系式，邊界條件就是遞歸終止條件，所以可以用遞歸來完成，遞歸存在重復調用，利用記憶化可以解決重復調用的問題，這就是方法二的記憶化搜索。
記憶化實現比較簡單，而且不會計算無用狀態，但遞歸也會受到棧的大小和遞推加回歸執行方式的約束，另外記憶化實現調用狀態的順序是按照實際需求而展開，沒有大局規劃，不利于進一步優化。
所以dp更常用的還是迭代法。狀態用二維數組表示，也就是說可以通過循環的方式求出每個狀態（通俗點稱呼就是填表）。
計算F[x][y]用到狀態F[x-1][y-1]與F[x-1][y]，這些元素在F[x][y]的上一行，也就是說要計算第x行的狀態的值，必須要先把第x-1行元素的值計算出來，因此我們可以先把第一行元素F[1][1]賦為 A[1][1]，再從第二行開始按照行從左到右遞增，從上到下遞增的順序通過循環計算出每一行的有效狀態即可。時間復雜度為 O ( N 2 ) O(N^2) O(N2)。
參考程序：
#include <iostream>
#include <algorithm>
using namespace std;
int A[1005][1005], F[1005][1005], N;
int main() {cin >> N;for (int i = 1; i <= N; i++)for (int j = 1; j <= i; j++)cin >> A[i][j];F[1][1] = A[1][1];for (int i = 2; i <= N; i++)for (int j = 1; j <= i; j++)F[i][j] = max(F[i - 1][j - 1], F[i - 1][j]) + A[i][j];int ans = 0;for (int i = 1; i <= N; i++)ans = max(ans, F[N][i]);cout << ans << endl;return 0;
}
滾動數組優化
根據之前得到的狀態轉移方程：F[x][y]=max{F[x-1][y-1],F[x-1][y]}+A[x,y]，
邊界條件：F[1][1]=A[1][1]，
發現在二維數組表示的轉移方程中，每個狀態都只和上一個狀態有關。而且每個狀態都只和前1個狀態有關，和前2個以及之前的所有狀態都無關。
所以可以將表示狀態的dp表用一維數組表示。狀態轉移方程變為
f[x]=max(f[x],f[x-1])+A[x,y]。
這種不改變空間復雜度，但可以極大程度地優化空間復雜度的狀態表示稱作滾動數組優化。
在填表的時候，需要將循環從右往左枚舉，才能保證每個狀態都是正確的。
因為都是正數，所以不必考慮邊界為0時造成的影響。如果存在負數，則可能需要對邊界情況做判斷，或取無窮小。
滾動數組優化參考程序：
#include<bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<vector<int> >A(1, vector<int>(2,0));vector<int>f(n+1,0);for (int i = 1; i <= n; i++) {A.push_back(vector<int>(i + 2, 0));for (int j = 1; j <= i; j++)cin >> A[i][j];}int ans = A[1][1];for (int i = 1; i <= n; i++) {for (int j = i; j >= 1; j--) {//逆向枚舉f[j] = max(f[j], f[j - 1]) + A[i][j];ans = max(ans, f[j]);}}cout << ans;return 0;
}
整體來說滾動數組優化的步驟：
- 先用二維或多維解決問題。
- 若狀態轉移方程的狀態只和上一層或上幾層格子有關，則可以考慮優化。否則不能優化。
- 若判斷出可以優化，則將原來的二維和多維狀態減少適當的維度，并看情況修改循環的枚舉順序。
當然不是所有的題都能做空間優化。
動態規劃（逆推）
這里思路和之前是一樣的，只是狀態的設定不同。
以這個樣例為例：
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
自底向上計算：（給出遞推式和終止條件）
從底層開始，本身數即為最大數；
倒數第二層的計算，取決于底層的數據，每次都取最大：
12 + 6 = 18 ， 13 + 14 = 27 ， 24 + 15 = 39 ， 24 + 8 = 32 12+6=18，13+14=27，24+15=39，24+8=32 12+6=18，13+14=27，24+15=39，24+8=32；
倒數第三層的計算，取決于底二層計算的數據，每次都取最大：
27 + 12 = 39 ， 39 + 7 = 46 ， 39 + 26 = 65 27+12=39，39+7=46，39+26=65 27+12=39，39+7=46，39+26=65，
倒數第四層的計算，取決于底三層計算的數據，每次都取最大：
46 + 11 = 57 ， 65 + 8 = 73 46+11=57，65+8=73 46+11=57，65+8=73，
最后的路徑：
5—>13—>8->26—>15—>24。
這是手搓簡單情況，復雜情況人的效率遠遠不及計算機，需要交給計算機來做。
數據結構及算法設計：
圖形轉化：直角三角形，便于搜索：向下、向右。
用三維數組表示數塔：
a[x][y][1]表示行、列及結點本身數據,
a[x][y][2]能夠取得最大值,
a[x][y][3]表示前進的方向，0表示向下，1表示向右。
算法實現：
數組初始化，輸入每個結點值及初始的最大路徑、前進方向為0；從倒數第二層開始向上一層求最大路徑，共循環N-1次；從頂向下，輸出路徑：究竟向下還是向右取決于列的值，若列的值比原先多則向右，否則向下。
#include<iostream>
using namespace std;
int main()
{int n, x, y;int a[1001][1001][4]={0};cin >> n;for (x = 1; x <= n; x++)//輸入數塔的初始值for (y = 1; y <= x; y++) {cin >> a[x][y][1];//1表示值a[x][y][2] = a[x][y][1];//2表示當前狀態，未經計算時默認是原來的數a[x][y][3] = 0;//3表示路徑走向，默認向下}for (x = n - 1; x >= 1; x--)//從倒數第二行開始推 for (y = 1; y <= x; y++)if (a[x + 1][y][2] > a[x + 1][y + 1][2]) {//選擇最大路徑值a[x][y][2] = a[x][y][2] + a[x + 1][y][2];a[x][y][3] = 0;}else {a[x][y][2] = a[x][y][2] + a[x + 1][y + 1][2];a[x][y][3] = 1;}cout << a[1][1][2] << endl;//輸出數塔最大值枚舉路徑，這題可忽略//y = 1;//for (x = 1; x <= n - 1; x++){//輸出數塔最大值的路徑// cout << a[x][y][1] << "->";// y = y + a[x][y][3];//下一行的列數//}//cout << a[n][y][1] << endl;return 0;
}
-策略模式)
)
