Dynamaic Programming

定義:

動態規劃是運籌學中用于求解決策過程中的最優化數學方法。作為算法設計技術，是一種使用多階段決策過程最優的通用方法。是解決最優化問題的重要工具。

動態規劃的特性:

• 無后效性
• 最優子結構

如何設計DP

動態規劃的本質，是對問題狀態的定義和狀態轉移方程的定義

• 1.設計狀態，實現狀態的定義

• 2.找到狀態轉移方程

• 動態規劃三要素:

  問題階段
  每個階段的狀態
  一個階段如何進入下一個階段的遞推關系式

多階段決策問題
初始狀態\(\rightarrow\)決策1\(\rightarrow\) 決策2 \(\rightarrow\)........\(\rightarrow\)決策n\(\rightarrow\)結束狀態

什么樣的問題適用DP

• 1)問題是由交疊的子問題所構成，大問題分解為小問題。

• 2)將交疊子問題的一次次求解\(\rightarrow\)子問題只求解一次，并將結果記錄保存。

• 3)利用空間(子問題存儲)來換取時間

實現案例分析

信件錯排問題

有 N 個 信 和 信封，它們被打亂，求錯誤裝信方式的數量
1.狀態定義:

dp[i] 表示前 i 個信和信封的錯誤方式數量
2.狀態轉移方程:
假設第 i 個信裝到第 j 個信封里面，而第 j 個信裝到第 k 個信封里面。根據 i 和 k 是否相等，有兩種情況

• i==k，交換 i 和 k 的信后，它們的信和信封在正確的位置，但是其余 i-2 封信有 dp[i-2] 種錯誤裝信的方式。由于 j 有 i-1 種取值，因此共有 (i-1)*dp[i-2] 種錯誤裝信方式
• i != k，交換 i 和 j 的信后，第 i 個信和信封在正確的位置，其余 i-1 封信有 dp[i-1] 種錯誤裝信方式。由于 j 有 i-1 種取值，因此共有 (i-1)*dp[i-1] 種錯誤裝信方式。

狀態轉移方程為
\[dp[i]=(i-1)*dp[i-2] + (i-1)*dp[i-1]\]

問題求解

先從最簡單的剪繩子(integer break product maximun)問題

int maxProductLength(int length){// 先進行判斷if(length<2) return 0;if(length==2) return 1;if(length==3) return 2;// 定義一個數組,存儲各個值// 交疊的子問題 的初始化int* product=new int[length+1];product[0]=0;product[1]=1;product[2]=2;product[3]=3;// 定義一個儲存最大值的變量int max=0;for(int i=4;i<length;++i){max=0;for(int j=1;j<=i/2;++j){// 遞推的表達式int product=product[i]*product[i-j];if(product>max)max=product;}product[i]=max;}max=product[length];delete[] product;return max; }

補充知識點:

多階段決策過程:

• 百科:多階段決策是指決策者在整個決策過程中做出時間上先后有別的多項決策。它通常比只需做出一項決策的單階段決策要復雜，它或是要決策者一次確定各階段應選擇的一串最優策略，或是找出表示一個過程內連續變化的一條控制變量曲線，或是確定適合不同狀態的靈活策略
• 總結：一次決策可以得到解的一部分，當做完所有決策就得到相應完整的解

轉載于:https://www.cnblogs.com/GeekDanny/p/10114076.html

總結

以上是生活随笔為你收集整理的动态规划-DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。