我是怎么向5歲侄女解釋動態(tài)規(guī)劃的？
我膨脹了，相信看了這個標題的同學，肯定忍不住破口大罵，什么瓜皮哦，dynamic programming這么簡單嗎，在我的印象里，尼瑪動態(tài)規(guī)劃是最難的。
>?背景
侄女5歲現在開始學習加減法了，每次做數學都離不開她的小手指，超過5的就開始數另一個手的手指，真是汗顏啊
有一天，我問她
“1+1+1+1+1等于多少？”
“搬起小拇指，就開始數了，5！”
“那么再加一個1呢？”
“當然是6了”?-脫口而出
“這次你怎么算這么快的？”
“剛剛不是5嗎，加1就是6了啊”
“所以你不需要重新計算，因為你記得之前的答案是5！動態(tài)規(guī)劃就是說：記住之前的東西可以節(jié)省時間”
進入正題
玩歸玩，鬧歸鬧，別拿dp開玩笑！
來瞅一眼科普中國科學百科的詞條解釋
動態(tài)規(guī)劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優(yōu)化的過程。20世紀50年代初，美國數學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應用極其廣泛，包括工程技術、經濟、工業(yè)生產、軍事以及自動化控制等領域，并在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統(tǒng)可靠性問題等中取得了顯著的效果。
看不完的童鞋跳過，咱整點簡單點的
其實剛剛這道題應該算是最簡單的動態(tài)規(guī)劃題目了。
我們可以看出這道題有什么特點呢？
我們知道之所以最后一步加1會計算的那么快，大部分要歸功于之前計算過答案是5，如果我們把問題歸納為一個子問題，我想要計算每一步的答案，就可以列出一個方程：f(x) = f(x -1) + 1, 大家別對f(x)發(fā)怵，就把它當做一個簡單的方法。
其中，f(x)為第幾步的值，設定一個初始值，x > 0, 則第一步
f(1) = 1;
f(2)?= 2;
...
f(6) =?6
在程序的世界里，用什么東東來存一個可以記錄之前結果值的數據結構呢？
顯而易見：數組唄。直接利用下標來存，巴適, 這就是動態(tài)規(guī)劃里的動態(tài)，規(guī)劃就是限定一些邊界和初始化。
來個訓練題
leecode 322: 你有三種硬幣，2元、5元、7元，每種硬幣足夠多，買一本書需要27元，用最少的硬幣組合
怎么感覺像是回到了小學應用題？
--簡單分析一下：?最小硬幣組合 -> 盡量用大的硬幣
這傻不拉幾的題誰出的，這么簡單
7+7+7=21,21+2+2+2=27， 6枚硬幣
臥槽
7+5+5+5+5=27， 5枚硬幣
我們可以很暴力的想一想，從大往小的算，可以加起來不超過27，比如
7+7+7+7 > 27?(排除）
7+7+7+5 或者?7?+7 +7+2+2+2?6枚
....
窮舉太慢了，還會涉及到很多的重復計算，如果我想要27以內的任何值最小的硬幣組合呢，想想都頭大了吧。
既然計算機可以通過內存保存之前的內容，又快，很明顯，我們開一個數組來保存之前的狀態(tài)。
重點預警
1.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
簡單的說，解動態(tài)規(guī)劃的時候需要開一個數組，數組的每個元素f[i]或者f[i][j]代表什么，類似數學題中x, y, z代表什么
解動態(tài)規(guī)劃需要兩個意識：
最后一步
子問題
最后一步
剛剛第一題不是說了嘛，最后一步的計算結果是5。對于這道題，雖然我們不知道最優(yōu)策略是什么，但是最優(yōu)策略肯定是K枚硬幣，a1, a2, ....ak面值加起來是27
所以一定有一枚最后的硬幣:ak.
除掉這么硬幣，前面硬幣的面值加起來是27-ak
關鍵點1：
我們不關心前面的k-1枚硬幣是怎么拼出27-ak的（可能有一種拼法，也可能有100種拼法），而且我們現在甚至還不知道ak和K, 但是我們確定前面的硬幣拼出了27-ak
關鍵點2：
因為是最優(yōu)策略， 所以拼出27-ak的硬幣數一定要最少，否則這就不是最優(yōu)策略了
子問題
所以我們就要求：最少用多少枚硬幣可以拼出27-ak
原問題是最少用多少枚硬幣拼出27
我們將原問題轉化了一個子問題，而且規(guī)模更小：27-ak
為了簡化定義， 我們設狀態(tài)f(x）=最少用多少枚硬幣拼出x
等等，我們還不知道最后的那枚硬幣ak是多少
很明顯，最后的那枚硬幣只能是2,5或者7
如果ak是2， f(27)應該是f(27-2)+1(1代表最后一枚硬幣2）
如果ak是5， f(27)應該是f(27-5)+1(1代表最后一枚硬幣5）
如果ak是7， f(27)應該是f(27-7)+1(1代表最后一枚硬幣7）
所以使用最少的硬幣數=f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}
1.2. 動態(tài)規(guī)劃組成部分2：轉移方程
設狀態(tài)f(x)=最少用多少枚硬幣拼出x
對于任意的x : f(X) = min{f(X-2)+1, f(X-5)+1, f(X-7)+1}
1.3. 動態(tài)規(guī)劃組成部分2：初始條件和邊界情況
提出問題
x-2, x-5, x-7 小于0怎么辦？
什么時候停下來？
1.3.1
如果不能拼出Y, 就定義f[Y] = 正無窮
例如f[-1], f[-2] = 正無窮
例如：拼不出f[1]=min{f(-1)+1, f(-3)+1, f(-6)+1}
初始條件：f[0] = 0
2.4. 動態(tài)規(guī)劃組成部分2：計算順序
計算：f[1], f[2], ... f[27]
當我們計算到f[x], f[x-2], f[x-5], f[x-7] 都已經得到結果了
如圖：
f[x] =?最少用多少枚硬幣拼出x
f[x] =?∞?表示無法用硬幣拼出x
參考代碼
public??static??int?coinChange(int?[]?A,?int?M?)?{
?int[]?f?=?new?int[M+1];
?int?n?=?A.length;
?f[0]?=?0;
?int?i,j;
?for?(i?=?1;?i<=M;?i++)?{
????f[i]?=?Integer.MAX_VALUE;
????for?(j?=?0;?j // 邊界條件判斷
????????if?(i?>=?A[j]?&&?f[i?-?A[j]]?!=?Integer.MAX_VALUE)?{
????????????f[i]?=?Math.min(f[i?-?A[j]]?+?1,?f[i]);
??????????//??System.out.println(i?+?"="?+f[i]);
????????}
????}
?}
?if?(f[M]?==?Integer.MAX_VALUE)?{
????f[M]?=?-1?;
?}
?return??f[M];
}
??
核心代碼就4行，是不是很簡單~
當然這道題也可以通過剪枝的方法實現，這里就不多贅述
再來個訓練題
還是再來一題吧，一道題也太隨意了~
leecode 62 ：不同路徑
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。
問總共有多少條不同的路徑？
看了上面的解題步驟，按部就班的來
2.1. 動態(tài)規(guī)劃組成部分1：確定狀態(tài)
最后一步
無論機器人用何種方式到達右下角，總有最后挪動的一步：-向右或者向下
如果所示，我們設右下角的坐標為(m-1,n-1)
那么最后一步的前一步機器人的位置在（m-2,n-1)或者(m-1,n-2)
子問題
那么，如果機器人有x種方式從左上角走到(m-2,n-1), 有Y種方式從左上角走到(m-1,n-2), 則機器人有X+Y的方式走到(m-1,n-1)
問題轉化為，機器人有多少種 方式從左上角走到(m-2,n-1)或者(m-1,m-2）
如果走到是(m-2,n-1)如圖：
我們可以直接干掉最后一列
同理如果是走到(m-1,n-2)行就減少一行。
狀態(tài)：
設f[i][j]為機器人有多少種方式從左上角走到(i,j)
2.2. 動態(tài)規(guī)劃組成部分2：轉移方程
對于任意一個格子：
f[i][j] = f[i-1][j] + f[i][j-1]
1 ? ? ? ? ?2 ? ? ? ? ? ?3
1代表機器人有多少種方式走到[i][j]
2代表機器人有多少種方式走到f[i-1][j]
3代表機器人有多少種方式走到f[i][j-1]
2.3. 動態(tài)規(guī)劃組成部分3：初始條件和邊界情況
初始條件：f[0][0]=1,因為機器人只有一個方式到左上角
邊界情況：i=0或j=0，則前一步只能有一個方向過來，也就是說第0行或者第0列，每走一步只有一種情況，則f[i][j] = 1,其他區(qū)域都滿足轉移方程。
3.4. 動態(tài)規(guī)劃組成部分4：計算順序
按行計算，為什么按行計算呢？
對于這道題來說，按行計算在計算到f[1][1]時，f[0][1]和f[1][0]都已經計算了，同樣按列計算這兩坐標也計算了，不用再次計算。
f[0][0] = ?1
計算第0行：f[0][0],f[0][1],...,f[0][n-1]
計算第1行：f[1][0],f[1][1],...,f[1][n-1]
...
計算第m-1行：f[m-1][0],f[m-1][1],...,f[m-1][n-1]
時間復雜度：O(mn)
參考代碼
public?int?uniquePaths(int?m,?int?n)?{
????int[][]?f?=?new?int[m][n];
????int?i,j;
????for?(i?=?0;?i<m;?i++)?{
????????for?(j?=?0;?jn;?j++)?{
????????????if?(i?==?0?||?j?==?0)?{
????????????????f[i][j]?=?1;
????????????}?else?{
????????????????f[i][j]?=?f[i?-1][j]?+?f[i][j-1];
????????????}
????????}
????}
????return?f[m-1][n-1];
}
總結一下
什么題可以選擇動態(tài)規(guī)劃來做？
1.計數
有多少種方式走到右下角
有多少種方法選出k個數是的和是sum
2.求最大值最小值
從左上角走到右下角路徑的最大數字和
最長上升子序列長度
3.求存在性
取石子游戲,先手是否必勝
能不能選出k個數使得和是sum
看到這里，基本上算是入門啦！