背景 侄女5歲現(xiàn)在開始學(xué)習(xí)加減法了，每次做數(shù)學(xué)都離不開她的小手指，超過5的就開始數(shù)另一個(gè)手的手指，真是汗顏啊 有一天，我問她 “1+1+1+1+1等于多少？” “搬起小拇指，就開始數(shù)了，5！” “那么再加一個(gè)1呢？” “當(dāng)然是6了” -脫口而出 “這次你怎么算這么快的？” “剛剛不是5嗎，加1就是6了啊” “所以你不需要重新計(jì)算，因?yàn)槟阌浀弥暗拇鸢甘?！動(dòng)態(tài)規(guī)劃就是說：記住之前的東西可以節(jié)省時(shí)間”
\color{red}{玩歸玩，鬧歸鬧，別拿dp開玩笑！}玩歸玩，鬧歸鬧，別拿dp開玩笑！ 來瞅一眼科普中國(guó)科學(xué)百科的詞條解釋 動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初，美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動(dòng)化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營(yíng)問題、資金管理問題、資源分配問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題等中取得了顯著的效果。 看不完的童鞋跳過，咱整點(diǎn)簡(jiǎn)單點(diǎn)的 其實(shí)剛剛這道題應(yīng)該算是最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃題目了。 我們可以看出這道題有什么特點(diǎn)呢？ 我們知道之所以最后一步加1會(huì)計(jì)算的那么快，大部分要?dú)w功于之前計(jì)算過答案是5，如果我們把問題歸納為一個(gè)子問題，我想要計(jì)算每一步的答案，就可以列出一個(gè)方程：f(x) = f(x -1) + 1, 大家別對(duì)f(x)發(fā)怵，就把它當(dāng)做一個(gè)簡(jiǎn)單的方法。 其中，f(x)為第幾步的值，設(shè)定一個(gè)初始值，x > 0, 則第一步 f(1) = 1; f(2) = 2; ... f(6) = 6 在程序的世界里，用什么東東來存一個(gè)可以記錄之前結(jié)果值的數(shù)據(jù)結(jié)構(gòu)呢？ 顯而易見：數(shù)組唄。直接利用下標(biāo)來存，巴適, 這就是動(dòng)態(tài)規(guī)劃里的動(dòng)態(tài)，規(guī)劃就是限定一些邊界和初始化。
\color{red}{別看了，這也是一道簡(jiǎn)單的題}別看了，這也是一道簡(jiǎn)單的題 leecode 322: 你有三種硬幣，2元、5元、7元，每種硬幣足夠多，買一本書需要27元，用最少的硬幣組合 怎么感覺像是回到了小學(xué)應(yīng)用題？ --簡(jiǎn)單分析一下： 最小硬幣組合 -> 盡量用大的硬幣 這傻不拉幾的題誰出的，這么簡(jiǎn)單 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枚 .... 窮舉太慢了，還會(huì)涉及到很多的重復(fù)計(jì)算，如果我想要27以內(nèi)的任何值最小的硬幣組合呢，想想都頭大了吧。 既然計(jì)算機(jī)可以通過內(nèi)存保存之前的內(nèi)容，又快，很明顯，我們開一個(gè)數(shù)組來保存之前的狀態(tài)。 重點(diǎn)預(yù)警 1.1. 動(dòng)態(tài)規(guī)劃組成部分1：確定狀態(tài) 簡(jiǎn)單的說，解動(dòng)態(tài)規(guī)劃的時(shí)候需要開一個(gè)數(shù)組，數(shù)組的每個(gè)元素f[i]或者f[i][j]代表什么，類似數(shù)學(xué)題中x, y, z代表什么 解動(dòng)態(tài)規(guī)劃需要兩個(gè)意識(shí)：
最后一步 剛剛第一題不是說了嘛，最后一步的計(jì)算結(jié)果是5。對(duì)于這道題，雖然我們不知道最優(yōu)策略是什么，但是最優(yōu)策略肯定是K枚硬幣，a1, a2, ....ak面值加起來是27 所以一定有一枚最后的硬幣:ak. 除掉這么硬幣，前面硬幣的面值加起來是27-ak 關(guān)鍵點(diǎn)1：
關(guān)鍵點(diǎn)2：
子問題
等等，我們還不知道最后的那枚硬幣ak是多少
所以使用最少的硬幣數(shù)=f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1} 1.2. 動(dòng)態(tài)規(guī)劃組成部分2：轉(zhuǎn)移方程 設(shè)狀態(tài)f(x)=最少用多少枚硬幣拼出x 對(duì)于任意的x : f(X) = min{f(X-2)+1, f(X-5)+1, f(X-7)+1} 1.3. 動(dòng)態(tài)規(guī)劃組成部分2：初始條件和邊界情況 提出問題
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. 動(dòng)態(tài)規(guī)劃組成部分2：計(jì)算順序 計(jì)算：f[1], f[2], ... f[27] 當(dāng)我們計(jì)算到f[x], f[x-2], f[x-5], f[x-7] 都已經(jīng)得到結(jié)果了 如圖： 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< n;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];
}
復(fù)制代碼?? \color{red}{核心代碼就4行，是不是很簡(jiǎn)單~}核心代碼就4行，是不是很簡(jiǎn)單 當(dāng)然這道題也可以通過剪枝的方法實(shí)現(xiàn)，這里就不多贅述
還是再來一題吧，一道題也太隨意了~ leecode 62 ：不同路徑 一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。 機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。 問總共有多少條不同的路徑？ 看了上面的解題步驟，按部就班的來 2.1. 動(dòng)態(tài)規(guī)劃組成部分1：確定狀態(tài) 最后一步 無論機(jī)器人用何種方式到達(dá)右下角，總有最后挪動(dòng)的一步：-向右或者向下 如果所示，我們?cè)O(shè)右下角的坐標(biāo)為(m-1,n-1) 那么最后一步的前一步機(jī)器人的位置在（m-2,n-1)或者(m-1,n-2) 子問題 那么，如果機(jī)器人有x種方式從左上角走到(m-2,n-1), 有Y種方式從左上角走到(m-1,n-2), 則機(jī)器人有X+Y的方式走到(m-1,n-1) 問題轉(zhuǎn)化為，機(jī)器人有多少種 方式從左上角走到(m-2,n-1)或者(m-1,m-2） 如果走到是(m-2,n-1)如圖： 我們可以直接干掉最后一列 同理如果是走到(m-1,n-2)行就減少一行。 狀態(tài)： 設(shè)f[i][j]為機(jī)器人有多少種方式從左上角走到(i,j) 2.2. 動(dòng)態(tài)規(guī)劃組成部分2：轉(zhuǎn)移方程 對(duì)于任意一個(gè)格子： f[i][j] = f[i-1][j] + f[i][j-1] 1 2 3 1代表機(jī)器人有多少種方式走到[i][j] 2代表機(jī)器人有多少種方式走到f[i-1][j] 3代表機(jī)器人有多少種方式走到f[i][j-1] 2.3. 動(dòng)態(tài)規(guī)劃組成部分3：初始條件和邊界情況 初始條件：f[0][0]=1,因?yàn)闄C(jī)器人只有一個(gè)方式到左上角 邊界情況：i=0或j=0，則前一步只能有一個(gè)方向過來，也就是說第0行或者第0列，每走一步只有一種情況，則f[i][j] = 1,其他區(qū)域都滿足轉(zhuǎn)移方程。 3.4. 動(dòng)態(tài)規(guī)劃組成部分4：計(jì)算順序 按行計(jì)算，為什么按行計(jì)算呢？ 對(duì)于這道題來說，按行計(jì)算在計(jì)算到f[1][1]時(shí)，f[0][1]和f[1][0]都已經(jīng)計(jì)算了，同樣按列計(jì)算這兩坐標(biāo)也計(jì)算了，不用再次計(jì)算。
時(shí)間復(fù)雜度：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; j< n; 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];
}
復(fù)制代碼總結(jié)一下 什么題可以選擇動(dòng)態(tài)規(guī)劃來做？ 1.計(jì)數(shù)
2.求最大值最小值
3.求存在性
|
|
|
