動态規劃算法

動态規劃總結

• 算法思想及步驟
• 典型例子
• • 數字三角形問題
  • 斐波那契數列
  • 數組最大不連續遞增子序列
  • 數組最大連續子序列和
  • 兩個字元串最大公共子序列
  • 背包問題
  • 找零錢問題：有幾種方法
• 總結

本文為自己的總結記錄，參考博文 動态規劃以及 六大算法之三：動态規劃總結很多。

算法思想及步驟

定義：
           

動态規劃算法的基本思想與分治法類似，也是将待求解的問題分解為若幹個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丢棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。

基本認識：
           

已知問題規模為n的前提A，求解一個未知解B。（我們用An表示“問題規模為n的已知條件”）

此時，如果把問題規模降到0，即已知A0，可以得到A0->B.

• 如果從A0添加一個元素，得到A1的變化過程。即A0->A1; 進而有A1->A2; A2->A3; …… ; Ai->Ai+1。這就是嚴格的歸納推理，也就是我們經常使用的數學歸納法；
• 對于Ai+1，隻需要它的上一個狀态Ai即可完成整個推理過程（而不需要更前序的狀态）。我們将這一模型稱為馬爾科夫模型。對應的推理過程叫做“貪心法”

然而，Ai與Ai+1往往不是互為充要條件，随着i的增加，有價值的前提資訊越來越少，我們無法僅僅通過上一個狀态得到下一個狀态，是以可以采用如下方案：

• {A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,…,Ai}->Ai+1。這種方式就是第二數學歸納法。

• 對于Ai+1需要前面的所有前序狀态才能完成推理過程。我們将這一模型稱為高階馬爾科夫模型。對應的推理過程叫做“動态規劃法”。

  上述兩種狀态轉移圖如下圖所示：

  

思想：

能采用動态規劃求解的問題的一般要具有3個性質：

(1) 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

(2) 無後效性：即某階段狀态一旦确定，就不受這個狀态以後決策的影響。也就是說，某狀态以後的過程不會影響以前的狀态，隻與目前狀态有關。

（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動态規劃适用的必要條件，但是如果沒有這條性質，動态規劃算法同其他算法相比就不具備優勢）

步驟

(1)劃分階段：按照問題的時間或空間特征，把問題分為若幹個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。

(2)确定狀态和狀态變量：将問題發展到各個階段時所處于的各種客觀情況用不同的狀态表示出來。當然，狀态的選擇要滿足無後效性。

(3)确定決策并寫出狀态轉移方程：因為決策和狀态轉移有着天然的聯系，狀态轉移就是根據上一階段的狀态和決策來導出本階段的狀态。是以如果确定了決策，狀态轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀态之間的關系來确定決策方法和狀态轉移方程。

(4)尋找邊界條件：給出的狀态轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

一般，隻要解決問題的階段、狀态和狀态轉移決策确定了，就可以寫出狀态轉移方程（包括邊界條件）。

實作步驟：
           

1、建立一個一維數組或者二維數組，儲存每一個子問題的結果，具體建立一維數組還是二維數組看題目而定，基本上如果題目中給出的是一個一維數組進行操作，就可以隻建立一個一維數組，如果題目中給出了兩個一維數組進行操作或者兩種不同類型的變量值，比如背包問題中的不同物體的體積與總體積，找零錢問題中的不同面值零錢與總錢數，這樣就需要建立一個二維數組。

注：需要建立二維數組的解法，都可以建立一個一維數組運用滾動數組的方式來解決，即一位數組中的值不停的變化。

2、設定數組邊界值，一維數組就是設定第一個數字，二維數組就是設定第一行跟第一列的值，特别的滾動一維數組是要設定整個數組的值，然後根據後面不同的資料加進來變幻成不同的值。

3、找出狀态轉換方程，也就是說找到每個狀态跟他上一個狀态的關系，根據狀态轉化方程寫出代碼。

4、傳回需要的值，一般是數組的最後一個或者二維數組的最右下角。

代碼基本架構：
           

for(j=1; j<=m; j=j+1) // 第一個階段  
  xn[j] = 初始值;  
for(i=n-1; i>=1; i=i-1)// 其他n-1個階段  
  for(j=1; j>=f(i); j=j+1)//f(i)與i有關的表達式    
    xi[j]=j=max（或min）{g(xi-[j1:j2]), ......, g(xi-1[jk:jk+1])};  
t = g(x1[j1:j2]); // 由子問題的最優解求解整個問題的最優解的方案  
print(x1[j1]);  
for(i=2; i<=n-1; i=i+1） {       
  t = t-xi-1[ji];       
  for(j=1; j>=f(i); j=j+1)       
    if(t=xi[ji])            
      break;}
           

典型例子

數字三角形問題

首先要選最大和，即每一步都要選擇一個最大值，滿足最優化原理，而且不影響後續的選擇，無後效性，對最終的結果有影響。符合動态規劃的思想。

可以看出每走一步就是一個階段，每一步的最優解就是選擇改行的最大值。

由于最後一行可以确定,可以當做邊界條件,是以我們自然而然想到遞歸求解。

大概思路：

但是這個方法存在大量的重複運算，時間複雜度為2的n次方。如果我們每次都把結果儲存下來,複雜度就會大大降低。

斐波那契數列

原先的遞歸

if(n == 0){
   return 0;   
}else if(n == 1){	
   return 1;    
}else{	
    return solutionFibonacci(n-1)+solutionFibonacci(n-2);    }
           

使用動态規劃

if(n == 0){
   return 0;   
}else if(n == 1){	
   return 1;    
}else{	
    int result[] = new int[n+1];
    result[0] = 0;
    result[1] = 1;
    for(int i=2;i<n;i++)
    {
      result[i] = result[i-1] + result[i-2];
    }
    return result[n];     
}
           

數組最大不連續遞增子序列

arr[] = {3,1,4,1,5,9,2,6,5}的最長遞增子序列長度為4。即為：1,4,5,9

設定一個數組temp，長度為原數組長度，數組第i個位置上的數字代表0…i上最長遞增子序列，當增加一個數字時，最大遞增子序列可能變成前面最大的遞增子序列+1，也可能就是前面的最大遞增子序列，這需要讓新增加進來的數字arr[i]跟前面所有數字比較大小，即當 arr[i] > arr[j]，temp[i] = max{temp[j]}+1，其中，j 的取值範圍為：0,1…i-1，當 arr[i] < arr[j]，temp[i] = max{temp[j]}，j 的取值範圍為：0,1…i-1，是以在狀态轉換方程為temp[i]=max{temp[i-1], temp[i-1]+1}。

就是在每個位置的最長遞增子序列，要麼是之前的+1，要麼直接用之前的數，比如arr數組，第一個為1，第二個比之前的小直接繼承前面的數1，第三個比第一個大加1，比第二個大加1，取最大的數2是以第三個數為2，第四個數比第一個第二個第三個都小，都繼承1最後取最大值1，以此類推。

public static int MaxChildArrayOrder(int a[]) {	
	int n = a.length;		
	int temp[] = new int[n];//temp[i]代表0...i上最長遞增子序列		
	for(int i=0;i<n;i++){	
		temp[i] = 1;//初始值都為1		
	}		
	for(int i=1;i<n;i++){		
		for(int j=0;j<i;j++){
			if(a[i]>a[j]&&temp[j]+1>temp[i])
			{//如果有a[i]比它前面所有的數都大，
			//則temp[i]為它前面的比它小的數的那一個temp+1取得的最大值 
			 temp[i]=temp[j]+1;				}			}		}		
			 int max = temp[0];//從temp數組裡取出最大的值		
			 for(int i=1;i<n;i++){			
			 if(temp[i]>max){			
			 	max =temp[i];		
			}		
		}		
		return max;	
	}
           

每一步都要跟之前的數比較來确定要+1還是直接繼承，滿足最優原理且無無後效性，而且對後面值的大小提供了有效的資訊，滿足動态規劃的思想。

數組最大連續子序列和

如arr[] = {6,-1,3,-4,-6,9,2,-2,5}的最大連續子序列和為14。即為：9,2,-2,5

建立一個數組a，長度為原數組長度，不同位置數字a[i]代表0…i上最大連續子序列和，a[0]=arr[0]設定一個最大值max，初始值為數組中的第一個數字。當進來一個新的數字arr[i+1]時，判斷到他前面數字子序列和a[i]+arr[i+1]跟arr[i+1]哪個大，前者大就保留前者，後者大就說明前面連續數字加起來都不如後者一個新進來的數字大，前面數字就可以舍棄，從arr[i+1]開始，每次比較完都跟max比較一下，最後的max就是最大值。

就是之前分治算法中的滑動視窗。

每一步都要比較sum+a[i]和 a[i]然後取較大值，滿足最優原理且無後效性，然後再通過比較更新max，為以後的取值提供有效的資訊，滿足動态規劃的思想。

public static int MaxContinueArraySum(int a[]) {
 int n = a.length;
 int max = a[0];
 int sum = a[0];
 for(int i=1;i<n;i++){
  sum = Math.max(sum+a[i], a[i]);
  if(sum>=max){
     max = sum;
  }
 }
 return max;
}
           

兩個字元串最大公共子序列

比如字元串1：BDCABA；字元串2：ABCBDAB，則這兩個字元串的最長公共子序列長度為4，最長公共子序列是：BCBA

具體思想：設 X=(x1,x2,…xn)和 Y={y1,y2,…ym} 是兩個序列，将 X 和 Y 的最長公共子序列記為LCS(X,Y)，如果 xn=ym，即X的最後一個元素與Y的最後一個元素相同，這說明該元素一定位于公共子序列中。是以，現在隻需要找：LCS(Xn-1，Ym-1)就好，LCS(X,Y)=LCS(Xn-1，Ym-1)+1；如果xn != ym，這下要麻煩一點，因為它産生了兩個子問題：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)。

動态規劃解法：先建立一個解空間即數組，因為給定的是兩個字元串即兩個一維數組存儲的資料，是以要建立一個二維數組，設字元串X有n個值，字元串Y有m個值，需要建立一個m+1*n+1的二維數組，二維數組每個位置（i，j）代表當長度為i的X子串與長度為j的Y的子串他們的最長公共子串，之是以要多建立一個是為了将邊界值填入進去，邊界值就是第一行跟第一列，指X長度為0或者Y長度為0時，自然需要填0，其他位置填數字時，當這兩個位置數字相同，dp[i][j] = dp[i-1][j-1]+1；當這兩個位置數字不相同時，dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])。最後二維數組最右下角的值就是最大子串。

每一個字元都要進行比較，然後确定該位置值時需要比較是否相同，相同時直接加一，不相同時則需要比較LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)，這是兩個子問題，滿足最優原理，無後效性。符合動态規劃的思想。

public class MaxTwoArraySameOrder {
 public static int MaxTwoArraySameOrderMethod(String str1,String str2) {
  int m = str1.length();
  int n = str2.length();
  /*
   * 定義一個二維數組儲存公共子序列長度
   * dp[i][j]表示字元串1從頭開始長度是i，字元串2從頭開始長度是j，這兩個字元串的最長公共子序列的長度
   * 設定數組行列比他們長度大一往二維數組中填寫數字時，每個位置的數字跟他上方或者左方或者左上方數字有關系，這樣處理邊界數字時不用處理這種情況，友善接下來的循環
   */
  int dp[][] = new int[m+1][n+1];
  /*
   * 初始化第一行第一列
   * dp[0,j]表示啥？表示字元串1的長度是0，字元串2的長度是j，這兩個字元串的最長公共子序列的長度是0，因為，字元串1 根本就沒有嘛
   */
  for(int i=0;i<=m;i++){
   dp[i][0] = 0;
  }
  for(int i=0;i<=n;i++){
   dp[0][i] = 0;
  }
  for(int i=1;i<=m;i++){
   for(int j=1;j<=n;j++){
    /*
     * 如果當c[i][j]時，字元串1從頭開始長度是i，字元串2從頭開始長度是j時他們最後一個字元相同
     * 就同時把他們向前移動一位，找c[i-1][j-1]時長度最大的再加一
     * 表現在二維數組中就是c[i][j]左上方的點
     */
    if(str1.charAt(i-1) == str2.charAt(j-1)){
     dp[i][j] = dp[i-1][j-1]+1;
     /*
      * 如果當c[i][j]時，他們最後一個字元不相同
      * 要将str1往前移動一位的c[i-1][j]的lcs長度，或者将str2往前移動一位的c[i][j-1]的lcs長度
      * 哪個長，将它賦給c[i][j]
      * 表現在二維數組中就是c[i][j]上方的點或者左方的點
      */
    }else{
     dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
    }
   }
  }
  return dp[m][n];
 }
 public static void main(String[] args) {
  String str1 = "BDCABA";
  String str2 = "ABCBDAB";
  int array = MaxTwoArraySameOrderMethod(str1,str2);
  System.out.println(array);
 }
}
           

背包問題

在N件物品取出若幹件放在容量為W的背包裡，每件物品的體積為W1，W2……Wn（Wi為整數），與之相對應的價值為P1,P2……Pn（Pi為整數），求背包能夠容納的最大價值。

像這種固定數值的組合問題，比如這個問題的W總容量，跟下個執行個體零錢問題的總錢數，都是适合用動态規劃來解決的問題，對于這樣的問題，動态規劃的解法就是：建立一個二維數組，橫坐标是從1開始到W，縱坐标是組成W的各種元素，本題中就是指W1，W2……Wn，數組中每個位置（i，j）的數字就是當組成元素隻有W1，W2……Wi，背包可放容量為j時的結果，本題中就是容納的最大價值。是以很容易分析出，當（i，j）時，如果Wi能放的下，空間減小，但是會增加Pi的價值，如果Wi不能放的下，空間不變，是（i-1，j）的價值，取其中最大值就好了，即狀态轉化方程為能放的下，dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+p[i])；放不下，dp[i][j] = dp[i-1][j]；

首先是分解原問題為子問題，将每加入一個物品視為每一步，目前有兩個變量，一個是體積j的變化，一個放入物品i後背包内物品總價值的變化。子問題控制一個變量，即目前體積确定的時候，背包容量為j時，前i個物品所能達到的最大價值。是以要建立一個二維數組。

其次是确定狀态，就是幾個變量之間的關系，就是我們上面說的背包容量為j時，前i個物品所能達到的最大價值。

确定一些邊界條件，比如初始值和結束值。初始值是dp[0][j]=0，背包裡沒有物品時，價值為0，結束值就是我們二維數組的最後一個值。

确定狀态轉移方程，第i個物品體積為w，價值為p，則狀态轉移方程為

j<w dp[i][j] = dp[i-1][j]//放不進去就是上一個物品的最大價值
j>w dp[i][j] = max{dp[i-1][j],dp[i-1][j-list[i].w]+v}//後面那個的意思是容量j減去一個和i相同的體積，再加上i的價值，就是相當于放入了一個i
           

public static int PackageHelper(int n,int w[],int p[],int v) {
  //設定一個二維數組，橫坐标代表從第一個物品開始放到第幾個物品，縱坐标代表背包還有多少容量，dp代表最大價值
  int dp[][] = new int[n+1][v+1];
  for(int i=1;i<n+1;i++){
   for(int j=1;j<=v;j++){
    if(j>=w[i]){
     /*
      * 當能放得下這個物品時，放下這個物品，價值增加，但是空間減小，最大價值是dp[i-1][j-w[i]]+p[i]
      * 當不放這個物品時，空間大，物品還是到i-1，最大價值是dp[i-1][j]
      * 比較這兩個大小，取最大的，就是dp[i][j]
      */
     dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
    }else{
     //如果放不下，就是放上一個物品時的dp
     dp[i][j] = dp[i-1][j];
    }
   }
  }
  return dp[n][v];
 }
           

動态規劃裡很多二維數組都可以用滾動數組來優化，滾動數組是一維的。長度為從1到W，初始值都是0，能裝得下i時，dp[j] = Math.max(dp[j], dp[j-w[i]]+p[i])；裝不下時，dp[j] = dp[j];

public static int PackageHelper2(int n,int w[],int p[],int v) {
  //設定一個二維數組，橫坐标代表從第一個物品開始放到第幾個物品，縱坐标代表背包還有多少容量，dp代表最大價值
  int dp[] = new int[v+1];
  for(int i=1;i<=n;i++){
   for(int j=v;j>0;j--){
    if(j>w[i]){
     dp[j] = Math.max(dp[j], dp[j-w[i]]+p[i]);
    }else{
     dp[j] = dp[j];
    }
   }
  }
  return dp[v];
 }
           

找零錢問題：有幾種方法

具體思路同背包問題，這裡隻分析一下動态轉化方程，能用這種零錢，分為用了這種零錢的方法跟沒用到這種零錢的方法，dp[i][j] = dp[i-1][j] + dp[i][j-num[i]]；如果不能用這種零錢，即所組成的面額小于目前零錢，直接等于不用這種零錢的數值，dp[i][j] = dp[i-1][j]。這裡要特别注意的是。1、開始填寫二維數組邊界值時，第一行是填寫隻用第一種面額零錢組成相應數額的方法，要注意是總數額除以第一種面額取餘為0才能組成，即如果第一種面額為2，不能組成3,5的數額等；2、填寫二維數組第一列時，代表到用到面額為i時，剩餘數額為0，即隻用i就可以組成相應數額，這也是一種方法，是以第一列的值，第一個為0，後面全為1。

public static int SmallMoney(int num[],int target) {
  int m = num.length;
  int dp[][] = new int[m][target+1];
  dp[0][0] = 1;
  for(int i=1;i<=target;i++){
   if(i%num[0] == 0){
    dp[0][i] = 1;//第一行數值填寫
   }else{
    dp[0][i] = 0;
   }
  }
  for(int i=0;i<m;i++){
   dp[i][0] = 1;//第一列數值填寫
  }
  for(int i=1;i<m;i++){
   for(int j=1;j<=target;j++){
    if(j<num[i]){
     dp[i][j] = dp[i-1][j];
    }else{
     dp[i][j] = dp[i-1][j] + dp[i][j-num[i]];
    }
   }
  }
  return dp[m-1][target];
 }
           

總結

解決動态規劃的問題

首先要确定這個問題是否适用于動态規劃，看他是否能分為好多步，每一步是否能夠求得目前的最優解，是否受後面的影響，是否能對後面的結果提供有效資訊。即是否滿足最優定理，是否無後效性，是否能有重疊子的問題。

拆分原問題，劃分為子問題，一定要找出其中的變量，其中的一個變量在另一個變量确定的情況下跟原問題有關，比如背包問題中，原問題是求背包裝最大價值的東西，子問題中一個變量就是，容量确定的情況下，前i個物品所能達到的最大價值。

确定狀态，什麼是狀态，狀态如何描述，比如背包問題，狀态就可以描述為，背包容量為j時，前i個物品所能達到的最大價值。就是要找到幾個變量之間的關系，最好将一個變量固定，來找和另一個變量之間的關系。

尋找邊界條件，比如初始值和結束值，一個變量為0時，他的值是多少，最終的結果存放在什麼地方，比如數組一般是存放在數組最後一位。

确定狀态轉移方程，首先是分情況，先寫出簡單的情況，然後複雜情況大機率是一個遞歸式，把這個遞歸式寫出來。