一.動態規劃原理<!--?xml version="1.0" encoding="UTF-8"?--> 多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最優化問題 ...
一.動態規劃原理
多階段決策問題中，各個階段採取的決策，一般來說是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的，故有“動態”的含義，稱這種解決多階段決策最優化問題的方法為動態規劃方法。
設計動態規划具體要滿足以下三個條件：
1.最優化原理（最優子結構性質） 最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。 2.無後效性將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱為無後效性。 3.子問題的重疊性 動態規劃將原來具有指數級時間複雜度的搜索演算法改進成了具有多項式時間複雜度的演算法。其中的關鍵在於解決冗餘，這是動態規划算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間複雜度要大於其它的演算法。動態規劃是一門思想，可以引用於很多比較複雜的解決方案中，我個人給他做的定位就是 1.空間換時間 2.解決問題由小到大，就片面到全面 下麵將從幾個例子作為切入點，如果對問題進行動態規劃
二.數字三角形
如圖，從9開始往下走，每次只能走相鄰的兩個節點，問如何走才能使數字之和最大化。
這個問題如果採用遍歷的方式那麼路徑將會呈指數級別增長,計算量非常大
20 x 21 x 22 ....x 2n-1 = 2 n(n-1) / 2
如果採用貪婪演算法每次選擇最大值 ,到達第四層的時候:9+15+8+9 < 9+12+10+18。這種方式只能得到局部最優解，而無法得到全局最優解。
顯然這兩種方式都不是最優的解決方式。如果採用DP(動態規劃)可以有效解決。
具體思想：我們從最底層往上走，從5五層到第四層開始比較，選擇最大的值：分別為19+2，18+10，9+10，5+16.然後基於這4個值繼續比較從第4層往第三層走，最後第三層變為18+10+10，18+10+6，5+16+8.按照這種思路依次走到第一層。
接下來由第4層往第3層走 分別選出最大的方案為28+10,29+6,21+8,如圖:
由第3層往第2層 分別選出最大的方案為38+12,34+15,如圖:
由第2層往第1層,可選出38+12,34+15 如圖:
最優方案 如圖:
這樣保證了，從第5層開始，每一次抉擇後的結構都是最優的結果，並且再也不會收到其他因素的音響值不會改變，且有由小到大最終每一個點的連線其實都是自他開始往下的最優解。
剛好滿足了DP演算法的三個特性:
1.最優化原理 2.無後向性 3子問題重疊
測試數據和代碼如下：
int array[5][5] = { 7,0,0,0,0, 3,8,0,0,0, 8,1,0,0,0, 2,7,4,4,0, 4,5,2,6,5, }; //動態劃分 for (int i = 4 - 1; i >= 0; i--) { for (int j = 0; j <= 4; j++) { array[i][j] = MAX(array[i + 1][j] , array[i+1][j+1]) + array[i][j]; } } NSLog(@"結果%d",array[0][0]);
三.01背包
有編號分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價值分別是6,3,5,4,6，現在給你個承重為10的背包，如何讓背包里裝入的物品具有最大的價值總和？
DP思想如下：拆分結構，尋找最優子元素。 最大結構是5個物品中尋找重量和為10且價值最大的物品，那麼最優子結構就是從1個物品選出重量和為1且價值最大的元素，如果條件滿足則就是他本身，不滿足則記為0，然後再一次往上遞增。
| 含義 | name | weight | value | 1kg | 2kg | 3kg | 4kg | 5kg | 6kg | 7kg | 8kg | 9kg | 10kg |
| abcde可選 | a | 2 | 6 | 0 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15（結束） |
| bcde可選 | b | 2 | 3 | 0 | 3 | 3 | 6 | 6 | 9 | 9 | 9 | 10 | 11 |
| cde可選 | c | 6 | 5 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 10 | 11 |
| de可選 | d | 5 | 4 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 10 | 10 |
| e可選 | e | 4 | 6 | 0（開始） | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
表格填寫的順序是從左下開始填寫直到右上結束，如果這個表格你能手動填寫完，那麼你就已經學會了01背包規劃方案。
為了方便理解，我們選擇幾個典型的進行描述：
表格從白色部分開始數
第5行第2列（e2）:可選物只有e,且有一個負重為2的背包，背包的最大價值為0，因為e本身的重量為4，放不下，這個表格故填0.
第2行第2列（b2）:可選物為b,c,d,e,且有一個負重為2的背包，背包最大價值為3，因為物品b重量為2剛好可以放下且價值為3，表格填3.
第1行第2列（a2）:可選物為a,b,c,d,e，且有一個負重為2的背包,背包最大價值為6，a和b都可以放入背包，且a的價值更大，選擇a，表格填6.
第1行第4列（a4）:可選物a,b,c,d,e， 且有一個負重為4的背包，a可以裝下，那麼到底裝不裝如a呢？我們需要做一個比較，假如裝下a，背包剩餘負重2，可選物為b,c,d,e, (b2)+6=9大於b4,選擇裝入a更好，所以a4的填入9。
第1行第5列（a6）:裝入a後剩餘重量為4，可選b,c,d,e. b(4)+6=12 > b6所以填入12.
若 f[i,j]表示在前i件物品中選擇若幹件放在承重為 j 的背包中，可以取得的最大價值。Pi表示第i件物品的價值，Wi表示第i件物品的重量，01背包核心方程式為：
f[i,j] = Max{ f[i-1,j-Wi] + Pi( j >= Wi ) , f[i-1,j] }
核心代碼如下：
- (void)viewDidLoad { [super viewDidLoad]; // Do any additional setup after loading the view, typically from a nib. //背包能裝入的總重量為10 5個物品的重量分別為2，2，6，5，4 價值為6，3，5，4，9 int knapsackSize = 10; MyItem * item1 = [MyItem myitemWithWeight:2 value:6]; MyItem * item2 = [MyItem myitemWithWeight:2 value:3]; MyItem * item3 = [MyItem myitemWithWeight:6 value:5]; MyItem * item4 = [MyItem myitemWithWeight:5 value:4]; MyItem * item5 = [MyItem myitemWithWeight:4 value:9]; NSArray* myitems = @[item1,item2,item3,item4,item5]; int value = [self getValueByKnapsack:myitems knapsackSize:knapsackSize]; NSLog(@"背包可裝入的最大價值%d",value); } //計算01背包能裝入的價格最優的值 MyItem（有兩個屬性value和weight） 可以用於被裝的元素 size背包一共能載重多少 -(int)getValueByKnapsack:(NSArray<MyItem *> *)myitems knapsackSize:(int)knapsackSize { //初始化一個 二維表格記錄每個最優策略的值 空間換時間 行數為總元素個數 列數為背包從0開始到總重量數 int ** a; a = (int **)malloc(sizeof(int *) * myitems.count); for (int i = 0; i < myitems.count; i++) { a[i] = (int *)malloc(sizeof(int) * knapsackSize + 1); a[i][0] = 0; } //最優子元素從只裝1個元素且載重只為1開始計算,保證最優子元素且無後向性 //遍歷重量從假如背包只能載重1的策略開始 for (int i = 1; i <= knapsackSize; i ++) { //可選物品從 0 到 所有 for (int j = 0; j < myitems.count; j++) { MyItem * item = myitems[j]; if (i < item.weight) { //背包裝不下的情況 if (j == 0) { //只有一個可選數據時 a[j][i] = 0; } else { //有多個可選數據 則使用上一個最優策略 a[j][i] = a[j-1][i]; } } else { //背包裝的下的情況 if (j == 0) { //只有一個可選數據 這個數據記錄為最優策略 a[j][i] = item.value; } else { //有多個可選擇的物品 則和上一個最優策略比較選擇最優策略 a[j][i] = MAX(a[j - 1][i], item.value + a[j - 1][i - item.weight]); } } } } //查詢最大值 int maxValue = 0; for (int i = 1; i <= knapsackSize; i ++) { for (int j = 0; j < myitems.count; j ++) { if (a[j][i] > maxValue) { maxValue = a[j][i]; } } } return maxValue; }
四.迪傑斯特拉最短路徑
求從1號點開始出發到後面所有點的最短路徑。
為了跟直觀的讓電腦來表示這組路徑，我們可以把他轉化為一個二維數組。
表示每個點到其他點的距離，無法直接到達通過∞表示
DP思想如下：
要求1到所有點的位置都是最最短路徑，那麼計算出來了後1隨便指定一個點都肯定是最優的，同樣在這個大組合中先拆分為子元素，子元素就是1到任意一個指定點比如1-2、1-3等等，然後從最小子元素開始算起。
用一個1位數組dis來表示1到各個點的路程，初始如下：
這個最小的子元素就是1-2，因為2號是離1最近的點，再沒有誰比他更近了，那麼dis[2]的值就成了確定了，以後再不會收誰的影響而改變了，1-2的距離等於1肯定是最短的路徑。
既然已經選擇了2，那麼再看看接下來從2號能到哪裡呢，有2-3，2-4. 還是和以前一樣開始比較看看誰才是最優解dis[2] + e[2][3] = 1 + 9 < dis[3], 1-2在2-3的方式比直接從1-3更優，因此dis[3] 更新為10，這個過程叫做“鬆弛”,1好到3號的路程就是dis[3]，通過2-3鬆弛成功。這就是迪傑斯特拉核心思想：通過邊來鬆弛各個路程。同樣dis[2] + e[2][4] = 4 < dis[4],因此dis[4]更新為4，鬆弛後的dis數組變為：
接下來繼續從剩下的3，4，5，6中選出距離1最近的點進比較。3，4，5，6最近的是4，dis[4]的值變成了確定值. 4可以經過的路線有4-3,4-5,4-6.按照之前的方案新一輪鬆弛之後dis數組變為:
接下來從剩下的3,5,6中選出距離1最近的點，點3。dis[3]變成了確定了，3有3-5。鬆弛後變為:
接下來從5，6中選出5,有5-6,鬆弛後變為:
最後還有6，鬆弛後變為:
最終這個鬆弛後的Dis數組就是從1到各個點的最佳路徑。
總結一下就是：每次知道離原點(上面例子就是1)最近的一個點，然後以該點為中心進行鬆弛，知道所有的點都走完一個輪詢，最終得到所有離原點最近的點。
核心代碼如下:
//構建鄰接矩陣 實際上為6,6 為了方便顯示所有從1~6開始計算 int matrix[7][7] = { 0,0,0,0,0,0,0, 0,0,1,12,999,999,999, 0,999,0,9,3,999,999, 0,999,999,0,999,5,999, 0,999,999,4,0,13,15, 0,999,999,999,999,0,4, 0,999,999,999,999,999,0 }; int book[7] = {0,0,0,0,0,0,0}; //記錄已經處理過的頂點 int dis[7] = {0,0,1,12,999,999,999}; //最佳路徑 預設是1到所有點的距離,999為無線大距離 註: 從1開始計算 int u = 0; for (int i = 1; i<=6; i++) { //表示查找次數 int min = 999; //尋找距離頂點1最近的點,且為鬆弛的點 for (int j = 1; j <=6; j++) { if (book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; //標誌U目前是距離1點最近且未處理的點, 馬上要用於處理 for (int k = 1; k <= 6 ; k++) { //查找U點可以到達的路權,且比較計算最優的dis if (matrix[u][k] < 999) { if (dis[u] + matrix[u][k] < dis[k]) { //如果1點到U點+U點到K點的距離 < dis[k]的距離,則更新最優距離 dis[k] = dis[u] + matrix[u][k]; } } } }
五.拓展：
最後再拓展一個小問題，你可以先不看思路嘗試著自己用動態劃分的思想解決。
對於一個從1到N的連續整數集合{1,2,3......,n-1,n},劃分為兩個子集，保證兩個集合的和相等。
例：n=3可分為{1,2}and{3}. 如果n=7可分為 {1,6,7} and {2,3,4,5} {2,5,7} and {1,3,4,6} {3,4,7} and {1,2,5,6} {1,2,4,7} and {3,5,6}
設計一個程式 輸入任意數劃分出可行的方案數，不能劃分則輸出0.
思路如下：
1+2+3.....+n = n*(n+1)/2, 兩個相同的子集任意一個的和肯定為總數和的一半，顧和一定為n*(n+1)/4，計作f(n). 所以這個題可以轉化為從集合中找出和為f(n)的子集合的數量，將他除以2就是我們可以得到的劃分方案。 這樣又可以用01背包的思想再次轉換，就成了背包問題了。物品1,2,3......,n， 價值分別為1,2,3......,n.給定一個稱重為f(n)的背包，問一共有多少種方案讓其剛好放滿，最後將方案除以2就是真確結果。
表格劃分如下：
