基礎算法 —— 3. 動态規劃

方法論

Like the divide-and-conquer method. But in contrast dynamic programming applies when the subproblems overlap. A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table. We typically apply dynamic programming to optimization problems.

we follow a sequence of four steps:

1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
4. Construct an optimal solution from computed information.

優化問題才具有最優子結構，即具有性質：利用子問題的最優結果可以組合成原問題的最優結果 才可以使用動态規劃。

一般而言，思考時使用遞歸的方式，實作時可以用遞歸或非遞歸。

Compute fashion

動态規劃的遞歸實作都是歸的過程中解決問題。是以每種動态規劃算法都至少有兩種實作方式。

top-down with memoization 與 bottom-up method

兩種實作方式：一般而言，0自底向上比自頂向下減少常數系數的時間複雜度，因為其不需要遞歸過程的開銷和維護表的狀态所需必要變量。而自頂向下可以減少對某些不可能的情況的計算。

Elements of dynamic programming

應用動态規劃的兩個關鍵點：optimal substructure and overlapping subproblems.

在它所依賴的所有子問題都得到解決之前，不會考慮子問題。也就是說，在考慮特定階段時，假設所有子問題的結果都已得出。

1. Optimal substructure if an optimal solution to the problem contains within it optimal

   solutions to subproblems.

   step:

   1. You show that a solution to the problem consists of making a choice.Making this choice leaves one or more subproblems to be solved. 确定轉移關系

   2. You suppose that for a given problem, you are given the choice that leads to an

      optimal solution. You do not concern yourself yet with how to determine this

      choice. You just assume that it has been given to you. 做出選擇

   3. Given this choice, you determine which subproblems ensue and how to best characterize the resulting space of subproblems.
   characteristic:
   1. how many subproblems an optimal solution to the original problem uses.

   2. how many choices we have in determining which subproblem(s) to use in an

      optimal solution.

   這個階段考慮的是 最優解的具體結構 和 **最優解的轉移關系 **。

   具體結構：要識别刻畫問題規模是單變量還是多變量。例如下面的鋼棒裁剪問題和最短路徑問題，都是單變量，而下面的矩陣鍊乘問題需要兩個變量。

   轉移關系：鋼棒裁剪問題是隻裁一刀分成（i 和 n-i ），産生一個子問題（n-i），不過卻有n個備選的 i 。而最短路徑問題也隻有一個子問題，不同階段選擇不同，A和C 都是4個選擇，而B是5個選擇。矩陣鍊乘問題 \(A_{ij}\) 有兩個子問題，和 \(j-i\) 個選擇。

2. overlapping subproblems

   子問題獨立：求最短簡單路徑和最長簡單路徑，最短簡單路徑就是子問題無關，獨立的，而最長簡單路徑子問題求解中是相關的，導緻某些求解資源被占用後子子問題不能求解

   子問題重疊：如果子問題不重疊，我們就可以使用分治算法。重疊的話就可以用動态規劃防止重複計算。

正确性的證明

You do so by supposing that each of the subproblem solutions is not optimal and then deriving a contradiction. In particular, by “cutting out” the nonoptimal solution to each subproblem and “pasting in” the optimal one, you show that you can get a better solution to the original problem, thus contradicting your supposition that you already had an optimal solution

running time

the running time of a dynamic-programming algorithm depends on the product of two factors: the number of subproblems overall and how many choices we look at for each subproblem.

裁鋼棒問題總共有n個子問題，子問題最多有n個備選方案，是以時間複雜度 \(O(n^2)\)

the subproblem graph Each vertex corresponds to a subproblem, and the choices for a subproblem are the edges incident to that subproblem. 用有向圖了解動态規劃

問題集

矩陣連乘問題

令\(A_{ij}\) 表示矩陣鍊乘 \(A_{i} A_{i+1} … A_{j}\) 。假設我們找到了一個解決方案，那麼最後一次兩矩陣相乘肯定為 \(A_{ik} * A_{k+1j} \space \space\space i<=k<j\) 由此，我們将原問題分為兩個子矩陣鍊乘 \(A_{ik},A_{k+1j}\) 。在[i, j) 中尋找使乘法次數最小的 k值。

這樣一來分治的思想就很好寫。

if(目前隻有一個矩陣){
    return 0;
}

int min = 0;
for(int k = i;k<j;++k){
	min = std::min(min,下一層Aik次數+下一層Ak+1j次數+Aik與Ak+1j相乘次數);	
}
return min;
           

不過注意到有大量的重複計算，子問題重疊的标志，由此，我們可以進一步動态規劃。

if(目前隻有一個矩陣){
    return 0;
}
if(a[i][j] == 0){
    int min = INT_MIN;
    for(int k = i;k<j;++k){
        min = std::min(min,下一層Aik次數+下一層Ak+1j次數+Aik與Ak+1j相乘次數);	
    }
    a[i][j] = min;
}
return a[i][j];
           

上面的直接由遞歸版改造的動态規劃也稱為 自頂向下的動态規劃，帶記憶的遞歸，備忘錄法等，下面看看另一種動态規劃實作。

for(矩陣鍊規模從2->n){
	for(對每個規模大小的矩陣鍊){
		for(對每個矩陣鍊中可能的k值){
			a[i][j] = min(a[i][j],a[i][k]+a[k+1][j]+兩矩陣相乘次數);
		}
    }
}
           

這種實作也稱 自底向上的動态規劃，填表法等，其特點就是從小規模問題構造大規模問題。

解結構：通過在上面記錄最小值的同時記錄k，然後通過下面的方法追溯解

if(目前隻有一個矩陣){
    輸出目前矩陣标号;
}
else{
    cout<<"(";
    以k為界限，輸出左部分；
    以k為界限，輸出右部分；
    cout<<")";
}

           

最長公共子序列

這個題的特點是假設解已經得出，由解的結構入手推理。然後可以自頂向下，設 \(C[i,j]\) 表示X 和 Y 的最長公共子序列的長度。則有 \(C[i,j] = \left\{\begin{array}\\C[i-1,j-1]+1 &X_i=Y_j \\\max(C[i-1,j],C[i,j-1])&X_i!=Y_j\end{array}\right.\)

普通的分治算法和自頂向下動态規劃比較像，這塊隻寫動态規劃的實作。

if(i<0||j<0){
	return 0;
}
if(a[i][j]未計算){
    if(x[i] == y[j]){
        a[i][j] = 進入下一層(i-1,j-1)  + 1
    }
    else{
        a[i][j] = max(下一層(i-1,j), 下一層(i,j-1));
    }
}
return a[i][j];

           

自底向上的實作

for(i:n){
	for(j:m){
		if(x[i] == y[j]){
			a[i][j] = a[i-1][j-1];
		}
		else{
			a[i][j] = max(a[i-1][j],a[i][j-1]);
		}
    }
}
return a[n][m];
           

解的結構，在記錄 a[i] [j] 的同時記錄是從[i-1][j-1] ; [i-1][j] ; [i][j-1] 三個方向中的哪一個來的

if(i<0||j<0){
	return;
}
else{
	if(從[i-1][j-1] 來的){
		cout<<x[i]; //x[i] == y[i]
	else if(從[i-1][j] 來的){
		進入下一層[i-1][j]
	else{
		進入下一層[i][j-1]
	}
}

           

最大子段和

前面分治一節寫過這個的分治解法，因為分治中有子問題重疊，并且具有最優解結構。是以有進一步使用動态規劃優化的可能。

直接想比較困難，不過我們可以稍微換種思路。設輸入的序列是 x，令 c[i] 表示含有 x[i] 的最大子段和，那麼c[i+1] 要麼是x[i+1] 要麼是 c[i] + x[i+1] ，兩個備選。這樣可以求出分别以 i 為尾部元素的最大子段和，由于我們要求的是整個數組的子段和，子段的尾部不确定。之後需要周遊 c 數組，找到最大的一項。

//自頂向下
if(i<0){  //目前隻有一個元素
	return 0;
}
if(c[i]未求解){
	c[i] = max(下一層(i-1) + x[i+1],x[i+1]);
}
return c[i];


//自底向上
for(;i<n;++i){   //逐漸增大尾端至n
	c[i+1] = max(c[i]+x[i+1],x[i+1]);
}


//最後都需要周遊一遍 C數組，找到最大的元素。
           

思考這個算法，在動态規劃的過程中，其是 \(O(n)\) 最後一次周遊也是 \(O(n)\) 是以，總時間就是 \(O(n)\) 相較于之前的分治 \(O(nlogn)\) 是一個改進。

解結構：在最後周遊c 數組中，通過最終結果和尾元素下标，根據x數組就能求出起始下标。

圖像壓縮變位壓縮存儲

分析這個問題，按照我們的分析步驟，首先我們可以看出最優解結構隻需一個變量 n 表示問題規模，再看為了确定最優解的備選共有 \(\min(n,256)\) 個。是以我們可以這樣寫。

即設 \(F[n]\) 表示當有n個像素時的最優解，\(j\) 表示最後一段有 \(j\) 個像素。 \(b\) 表示最後一段單個像素所占的最大位數。 \(F[n] = \min\limits_{1<=j<=\min(n,256)}(F[n-j]+j*b+11)\)

是以，自頂向下的算法如下

if(如果目前像素個數為0){
	return 0;
}
if(F[n]未求解){
	int min = INT_MAX;
	int b = INT_MIN;
	for(對j所有可能的取值){
		用公式更新b的值
		min = std::min(min,進入下一層(n-j)+j*b+11); //更新目前min 的值 
	}
	将min 賦給F
}
return F[n]
           

自底向上

for(像素個數規模不斷增大(i->n)){
	int min = INT_MIN;
	for(對目前規模所有可能的j值){
		更新b 的值
		min = std::min(min,上一段(F[i-j])+j*b+11);
    }
    F[i] = j;
}
return F[n];
           

解結構：在真正更新 min 時，記錄此時的 i-j 即得到劃分下标。

電路布線問題

注意題幹要求隻是使第一層的排線盡可能多，這樣的問題實際上是最大不相交子集。

我們要留意的是如何用數學語言描述問題：可以将每條線的上端點用 i 表示，第i 條線既是第i個端點所在的線，j 表示第 i 條線的另一端點。

接下來考慮如何遞推：經過分析可知，一條線隻有選或不選兩種可能。為了滿足不相交的特性。當我們将第 i 條線選入集合内，意味着解中剩下的線的下端點都不能超過 i 所對應的 j 。如果不選，那麼問題規模 i 減小。而目前可用的下端 j 不變。

故此，我們可以寫出遞推關系式。令 \(F[i][j]\) 表示上下端點分别為 i j 時最多的連線數。則 \(F[i][j] = max(F[i-1][j-1]+1,F[i-1][j])\)

//遞歸版
if(i==0){
	return 0;
}
else if(F[i][j] == 0){
	F[i][j] = max(下一層(i-1,j),下一層(i-1,j-1)+1);
}
return F[i][j];

//非遞歸版
for(i: 1->n){
	for(j: 1->n){
        F[i][j] = max(F[i-1][j],F[i-1][j-1]+1);
	}
}
           

解的記錄：在max 比較大小時可以記錄解。然後可以根據記錄的數組進行回溯。

鋼棒裁剪問題

我們的思路是将裁一刀鋼棒分為兩部分，左部分不再切割，而右部分可繼續切割、相當于子問題。

是以，刻畫問題規模隻需要一個變量即鋼棒的長度n。而切的這一刀卻有n個備選位置。

int CutMax_r(int *arr,int n){
    if(n == 0){
        return 0;
    }
    int max = -1;
    for(int i=1;i<=n;++i){
        max = std::max(max,arr[i]+CutMax_r(arr,n-i));
    }
    return max;
}
int CutMax_dT(int *arr,int *brr,int n){
    if(n == 0){
        return 0;
    }
    if(brr[n]==-1){
        for(int i=1;i<=n;++i){
            brr[n] = std::max(brr[n],arr[i]+CutMax_r(arr,n-i));
        }
    }
    return brr[n];
}
int CutMax_dB(int*arr,int *brr,int *s,int n){
    brr[0] = 0;
    for(int i=1;i<=n;++i){
        int res = -1;
        for(int j=1;j<=i;++j){
            if (res < arr[j] + brr[i - j]){
                s[i] = j;
                res = arr[j]+brr[i-j];
            }
            // brr[i] = std::max(brr[i],arr[j]+brr[i-j]);
        }
        brr[i] = res;
    }
    return brr[n];
}
int Trace(int *s,int n){
    while(n>0){
        cout<<s[n]<<' ';
        n -= s[n];
    }
}
int CutMax(int *arr,int n){
    int res = -1;
    // res = CutMax_r(arr,n-1);

    int *brr = new int[n]();
    memset(brr,-1,sizeof(int )*(n));
    int *s = new int[n]();
    memset(s,-1,sizeof(int )*(n));
    // res = CutMax_dT(arr,brr,n-1);
    res = CutMax_dB(arr,brr,s,n-1);
    Trace(s,n-1);
    return res;
}   
           

子問題：

1. 證明原始遞歸算法的時間複雜度。

   

   利用替換法 設 T(n ) <= cn^2.

2. 舉反例證明貪心算法在這個問題上不一定能得到最優解。

   問題主要出現在當兩種長度的機關價格相同。假設棒的長度為4. 不同尺寸的價值分别為 1，3，6，8 ，那麼根據貪心算法，可能選擇1-3切，也可能不切，1-3切就不是最優解

3. 加一個條件，每次切割都會有固定的花費。求這種情況下的最優解。

   切一刀的花費可以看做，切一刀的負收益。

4. 修改一下，讓它不僅傳回解，同時傳回解的結構。

   可以将解和解結構封裝到結構體裡面傳回。

5. 通過遞歸版動态規劃實作斐波那契數列的計算。并且子問題圖中有多少個節點和多少條邊。

   實作沒什麼好說的，子問題圖中有n個節點，2(n-2)條邊。

最短路徑問題

我們選擇使終點不變，逐漸擴大起點從 C -> S。刻畫問題規模隻需要一個變量表示階段數，而本例題每個階段的有8個備選。

遞推方程： S-T 最短 = S-C最短 + C-T 最短

投資問題

我們可以假設 \(F[n][m]\) 表示将m元錢投給n個項目所得的最大收益，那麼刻畫問題規模需要兩個變量，m和n 。而備選的方案 x 要滿足 \(0<= x <= \min(f_n,m)\) 其中 \(f_n\) 表示第n 個項目最多投資的錢數。

故此，可得到遞推方程 \(F[n,m] = \max\limits_{0<= x <= \min(f_n,m)}(f_n(x)+F_[n-1][m-x])\)

背包問題

背包問題有點大，這裡隻是簡單的提一下簡單的三種類型。先從一個例子入手。

有一個背包，\(n\) 個物品，第 \(i\) 個物品的重量和價值分别為 \(w_i\) 和 \(v_i\) ，每個物品隻有一件。假設背包總重量限制為 \(b\) 問如何挑選物品使得背包總價值最大。

先說可能的思路，一看到這個問題我第一反應想到了排列問題。一個物品選或不選剛好對應比特位01狀态。是以可以用遞歸模拟二叉樹。

現在考慮另一種解法 假設 \(F[n,b]\) 表示有n個物品可供挑選，背包空間為b時的最大收益，那麼該問題的狀态轉移方程可如下定義\(F[n,b] = max(F[n-1,b],F[n-1,b-w[n]]+v[n])\) 等式右邊表示裝第n 個物品和不裝第n個物品的不同收益的最大值。

接下來我們考慮另一個類似問題，假設每個物品有無限件，這時又該如何操作呢？

\(F[n,b] = \max\limits_{0<=k<= \lfloor b/w[n]\rfloor}(F[n-1,b-k*w[n]]+k*v[n] )\) ，如果你令k隻能取0-1的話其實這個方程和上面的方程沒什麼差別。

再推廣一下，假設物品的數量不全為1，也不是無限件。那麼隻需要在上面的方程中對k的值再進一步限定就好。

總結一下對于k 隻能取0-1狀态的話其實稱為0-1背包問題，物品有無限件對應完全背包問題，物品有特定件稱為多重背包問題，物品可切片對應 部分背包問題。

關于背包問題更多見 背包九講