【动态规划】不信看完你还不懂动态规划
1.什么是動(dòng)態(tài)規(guī)劃？
維基百科：動(dòng)態(tài)規(guī)劃(Dynamic programming，簡(jiǎn)稱DP)是一種通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式求解復(fù)雜問題的方法。
使用場(chǎng)景：動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。
dynamic programming is a m·· ethod for solving a complex problem by breaking it down into a collection of simpler subproblems.
簡(jiǎn)單來說，動(dòng)態(tài)規(guī)劃其實(shí)就是，給定一個(gè)問題，我們把它拆成一個(gè)個(gè)子問題，直到子問題可以直接解決，然后把子問題答案保存起來，以減少重復(fù)計(jì)算。再根據(jù)子問題答案反推，得出原問題解的一種方法。
動(dòng)態(tài)規(guī)劃最核心的思想，就在于拆分子問題，記住過往，減少重復(fù)計(jì)算。
一般這些子問題很相似，可以通過函數(shù)關(guān)系式遞推出來。動(dòng)態(tài)規(guī)劃就致力于解決每個(gè)子問題一次，減少重復(fù)計(jì)算，比如`斐波那契數(shù)列`，就可以看做入門級(jí)的經(jīng)典動(dòng)態(tài)規(guī)劃問題。
2.動(dòng)態(tài)規(guī)劃3個(gè)核心點(diǎn)
- 確定邊界--退出條件
- 確定最優(yōu)子結(jié)構(gòu)--拆分子問題
- 狀態(tài)轉(zhuǎn)移方程--子問題合并方式，即子問題和原問題關(guān)系，將子問題結(jié)果合并得出最終答案
對(duì)于這個(gè)3點(diǎn)，后面會(huì)做一一解釋，請(qǐng)看我道來。
3.從「錢」講起
一個(gè)算法星球的央行發(fā)行了奇葩幣，幣值分別為1、5、11，要湊夠15元最少要幾個(gè)貨幣？
它的問題其實(shí)是「給定一組面額的硬幣,我們用現(xiàn)有的幣值湊出n最少需要多少個(gè)幣」。
我們要湊夠這個(gè) n,只要 n 不為0,那么總會(huì)有處在最后一個(gè)的硬幣,這個(gè)硬幣恰好湊成了 n,比如我們用 {11,1,1,1,1} 來湊15,前面我們拿出 {11,1,1,1},最后我們拿出 {1} 正好湊成 15。
?如果用 {5,5,5} 來湊15,最后一個(gè)硬幣就是5,我們按照這個(gè)思路捋一捋,：
- 那么假設(shè)最后一個(gè)硬幣為11的話，那么剩下4，這個(gè)時(shí)候問題又變成了，我們湊出 n-11 最少需要多少個(gè)幣,此時(shí)n=4，我們只能取出4個(gè)面值為1的幣
- 如果假設(shè)最后一個(gè)硬幣為 5 的話，這個(gè)時(shí)候問題又變成了，我們用現(xiàn)有的幣值湊出 n-5 最少需要多少個(gè)幣
大家發(fā)現(xiàn)了沒有，我們的問題提可以不斷被分解為「我們用現(xiàn)有的幣值湊出 n 最少需要多少個(gè)幣」，比如我們用 f(n) 函數(shù)代表 「湊出 n 最少需要多少個(gè)幣」.
把「原有的大問題逐漸分解成類似的但是規(guī)模更小的子問題」這就是最優(yōu)子結(jié)構(gòu),我們可以通過自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。
這個(gè)時(shí)候我們分別假設(shè) 1、5、11 三種面值的幣分別為最后一個(gè)硬幣的情況：
- 最后一枚硬幣的面額為 11: min = f(4) + 1
- 最后一枚硬幣的面額為 5: min = f(10) + 1
- 最后一枚硬幣的面額為 1: min = f(14) + 1
這個(gè)時(shí)候大家發(fā)現(xiàn)問題所在了嗎?最少找零 min 與 f(4)、f(10)、f(14) 三個(gè)函數(shù)解中的最小值是有關(guān)的，畢竟后面的「+1」是大家都有的。
假設(shè)湊的硬幣總額為 n，那么 f(4) = f(n-11)、f(10) = f(n-5)、f(14) = f(n-1)，我們得出以下公式:
f(n) = min{f(n-1), f(n-5), f(n-11)} + 1?我們?cè)倬唧w到上面公式中 f(n-1) 湊夠它的最小硬幣數(shù)量是多少,是不是又變成下面這個(gè)公式:
f(n-1) = min{f(n-1-1), f(n-1-5), f(n-1-11)} + 1以此類推...
這真是似曾相識(shí),這不就是遞歸嗎?是的,我們可以通過遞歸來求出最少找零問題的解。
4.遞歸解法
public static int coinChange(int n) {if (n <= 0) return 0;int min = Integer.MAX_VALUE;if (n >= 1) {min = Math.min(coinChange(n - 1) + 1, min);}if (n >= 5) {min = Math.min(coinChange(n - 5) + 1, min);}if (n >= 11) {min = Math.min(coinChange(n - 11) + 1, min);}return min; }- 當(dāng)n=0的時(shí)候,直接返回0,增加程序魯棒性
- 我們先設(shè)最少找零 min 為 「無限大」，方便之后Math.min 求最小值
- 當(dāng)最后一個(gè)硬幣為1的時(shí)候,我們遞歸 min = Math.min(f(n-1) + 1, min),求此種情況下的最小找零
- 當(dāng)最后一個(gè)硬幣為5的時(shí)候,我們遞歸 min = Math.min(f(n-5) + 1, min),求此種情況下的最小找零
- 當(dāng)最后一個(gè)硬幣為11的時(shí)候,我們遞歸 min = Math.min(f(n-11) + 1, min),求此種情況下的最小找零
遞歸的弊端
我們看似已經(jīng)把問題解決了,但是別著急，我們繼續(xù)測(cè)試，當(dāng)n越來越大時(shí)，執(zhí)行時(shí)間幾何數(shù)增長，而且最后還出現(xiàn)棧溢出的情況。所以為什么會(huì)造成如此長的執(zhí)行耗時(shí)?歸根到底是遞歸算法的低效導(dǎo)致的。
我們?nèi)绻?jì)算f(70)就需要分別計(jì)算最后一個(gè)幣為1、5、11三種面值時(shí)的不同情況，而這三種不同情況作為子問題又可以被分解為三種情況，依次類推...這樣的算法復(fù)雜度有 O(3?),這是極為低效的。
我們?cè)僮屑?xì)看圖:
我們用紅色標(biāo)出來的都是相同的計(jì)算函數(shù)，比如有兩個(gè)f(64)、f(58)、f(54)，這些都是重復(fù)的,這些只是我們整個(gè)計(jì)算體系下的冰山一角，我們還有非常多的重復(fù)計(jì)算沒辦法在圖中展示出來。
可見我們重復(fù)計(jì)算了非常多的無效函數(shù)，浪費(fèi)了算力。
我們不妨再舉一個(gè)簡(jiǎn)單的例子，比如我們要計(jì)算 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」的和。
我們開始數(shù)數(shù)...,直到我們數(shù)出上面計(jì)算的和為 8，那么，我們?cè)僭谏鲜?「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」 后面 「+ 1」，那么和是多少？
這個(gè)時(shí)候你肯定數(shù)都不會(huì)數(shù)，脫口而出「9」。
為什么我們?cè)诤竺娴挠?jì)算這么快？是因?yàn)槲覀円呀?jīng)在大腦中記住了之前的結(jié)果 「8」，我們只需要計(jì)算「8 + 1」即可，這避免了我們重復(fù)去計(jì)算前面的已經(jīng)計(jì)算過的內(nèi)容。
我們用的遞歸像什么？像繼續(xù)數(shù)「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」來計(jì)算出「9」，這是非常耗時(shí)的。
我們假設(shè)用 m 種面值的硬幣湊 n 最少需要多少硬幣，在上述問題下遞歸的時(shí)間復(fù)雜度是驚人的O(n?),指數(shù)級(jí)的時(shí)間復(fù)雜度可以說是最差的時(shí)間復(fù)雜度之一了。我們已經(jīng)發(fā)現(xiàn)問題所在了,大量的重復(fù)計(jì)算導(dǎo)致時(shí)間復(fù)雜度奇高,我們必須想辦法解決這個(gè)問題。
5.備忘錄與遞歸
既然已經(jīng)知道存在大量冗余計(jì)算了,那么我們可不可以建立一個(gè)備忘錄,把計(jì)算過的答案記錄在備忘錄中,再有我們需要答案的時(shí)候,我們?nèi)渫浿胁檎?如果能查找到就直接返回答案,這樣就避免了重復(fù)計(jì)算,這就是算法中典型的空間換時(shí)間的思維。
有了思路后,其實(shí)代碼實(shí)現(xiàn)非常簡(jiǎn)單,我們只需要建立一個(gè)緩存?zhèn)渫?在函數(shù)內(nèi)部校驗(yàn)校驗(yàn)是否存在在結(jié)果,如果存在返回即可。
public class Cions {public static void main(String[] args) {int a = coinChange(70);System.out.println(a);}private static HashMap<Integer,Integer> cache = new HashMap<>();public static int coinChange(int amount) {return makeChange(amount);}public static int makeChange(int amount) {if (amount <= 0) return 0;// 校驗(yàn)是否已經(jīng)在備忘錄中存在結(jié)果,如果存在返回即可if(cache.get(amount) != null) return cache.get(amount);int min = Integer.MAX_VALUE;if (amount >= 1) {min = Math.min(makeChange(amount-1) + 1, min);}if (amount >= 5) {min = Math.min(makeChange(amount-5) + 1, min);}if (amount >= 11) {min = Math.min(makeChange(amount-11) + 1, min);}cache.put(amount, min);return min;} }實(shí)際上利用備忘錄來解決遞歸重復(fù)計(jì)算的問題叫做「記憶化搜索」。
這個(gè)方法本質(zhì)上跟回溯法的「剪枝」是一個(gè)目的，就是把上圖中存在重復(fù)的節(jié)點(diǎn)全部剔除,只保留一個(gè)節(jié)點(diǎn)即可,當(dāng)然上圖沒辦法把所有節(jié)點(diǎn)全部展示出來,如果剔除全部重復(fù)節(jié)點(diǎn)最后只會(huì)留下線性的節(jié)點(diǎn)形式:
?帶備忘錄的遞歸算法時(shí)間復(fù)雜度只有O(n),已經(jīng)跟動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度相差不大了。
那么這不就可以了嗎？為什么還要搞動(dòng)態(tài)規(guī)劃？還記得我們上面提到遞歸的另一大問題嗎？
爆棧！編程語言棧的深度是有限的,即使我們進(jìn)行了剪枝，在五位數(shù)以上的情況下就會(huì)再次產(chǎn)生爆棧的情況,這導(dǎo)致遞歸根本無法完成大規(guī)模的計(jì)算任務(wù)。
這是遞歸的計(jì)算形式?jīng)Q定的,我們這里的遞歸是「自頂向下」的計(jì)算思路，即從 f(70) f(69)...f(1) 逐步分解。「自頂向下」的思路在另一種算法思想中非常常見，那就是分治算法。
這個(gè)思路在這里并不完全適用,我們需要一種「自底向上」的思路來解決問題。「自底向上」就是 f(1) ... f(70) f(69)通過小規(guī)模問題遞推來解決大規(guī)模問題,動(dòng)態(tài)規(guī)劃通常是用迭代取代遞歸來解決問題。
除此之外,遞歸+備忘錄的另一個(gè)缺陷就是再?zèng)]有優(yōu)化空間了，因?yàn)樵谧顗牡那闆r下，遞歸的最大深度是 n。因此，我們需要系統(tǒng)遞歸堆棧使用 O(n) 的空間,這是遞歸形式?jīng)Q定的,而換成迭代之后我們根本不需要如此多的的儲(chǔ)存空間,我們可以繼續(xù)往下看。
6.動(dòng)態(tài)規(guī)劃算法
還記得上面我們利用備忘錄緩存之后各個(gè)節(jié)點(diǎn)的形式是什么樣的嗎,我們把它這個(gè)「?jìng)渫洝棺鳛橐粡埍?#xff0c;這張表就叫做 DP table,如下:
?注意: 上圖中 f[n] 代表湊夠 n 最少需要多少幣的函數(shù),方塊內(nèi)的數(shù)字代表函數(shù)的結(jié)果
我們不妨在上圖中找找規(guī)律?
我們觀察f[1]: f[1] = min(f[0], f[-5], f[-11]) + 1
由于f[-5] 這種負(fù)數(shù)是不存在的,我們都設(shè)為正無窮大,那么f[1] = 1。
再看看f[5]: f[1] = min(f[4], f[0], f[-6]) + 1,這實(shí)際是在求f[4] = 4、f[0] = 0、f[-6]=Infinity中最小的值即0，最后加上1，即1，那么f[5] = 1。
狀態(tài)轉(zhuǎn)移方程
發(fā)現(xiàn)了嗎？我們?nèi)魏我粋€(gè)節(jié)點(diǎn)都可以通過之前的節(jié)點(diǎn)來推導(dǎo)出來，根本無需再做重復(fù)計(jì)算，這個(gè)相關(guān)的方程是:
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1還記得我們提到的動(dòng)態(tài)規(guī)劃有更大的優(yōu)化空間嗎?遞歸+備忘錄由于遞歸深度的原因需要 O(n) 的空間復(fù)雜度,但是基于迭代的動(dòng)態(tài)規(guī)劃只需要常數(shù)級(jí)別的復(fù)雜度。
看下圖,比如我們求解 f(70),只需要前面三個(gè)解,即 f(59) f(69) f(65) 套用公式即可求得,那么 f(0)f(1) ... f(58) 根本就沒有用了,我們可以不再儲(chǔ)存它們占用額外空間,這就留下了我們優(yōu)化的空間。
?上面的方程就是動(dòng)態(tài)轉(zhuǎn)移方程,而解決動(dòng)態(tài)規(guī)劃題目的鑰匙也正是這個(gè)動(dòng)態(tài)轉(zhuǎn)移方程。
當(dāng)然,如果你只推導(dǎo)出了動(dòng)態(tài)轉(zhuǎn)移方程基本上可以把動(dòng)態(tài)規(guī)劃題做出來了,但是往往很多人卻做不對(duì),這是為什么?這就得考慮邊界問題。
邊界問題
部分的邊界問題其實(shí)我們?cè)谏厦娴牟糠忠呀?jīng)給出解決方案了,針對(duì)這個(gè)找零問題我們有以下邊界問題。
處理f[n]中n為負(fù)數(shù)的問題：
凡是n為負(fù)數(shù)的情況,一律將f[n]視為正無窮大。?
因?yàn)檎Ｇ闆r下我們是不會(huì)有下角標(biāo)為負(fù)數(shù)的數(shù)組的,所以其實(shí) n 為負(fù)數(shù)的 f[n] 根本就不存在
又因?yàn)槲覀円笞钌僬伊?為了排除這種不存在的情況,也便于我們計(jì)算
我們直接將其視為正無窮大,可以最大程度方便我們的動(dòng)態(tài)轉(zhuǎn)移方程的實(shí)現(xiàn)。
處理f[n]中n為0的問題
n=0 的情況屬于動(dòng)態(tài)轉(zhuǎn)移方程的初始條件
初始條件也就是動(dòng)態(tài)轉(zhuǎn)移方程無法處理的特殊情況
比如我們?nèi)绻麤]有這個(gè)初始條件,我們的方程是這樣的: f[0] = min(f[-1], f[-5], f[-11]) + 1
最小的也是正無窮大,這是特殊情況無法處理,因此我們只能人肉設(shè)置初始條件。
處理好邊界問題我們就可以得到完整的動(dòng)態(tài)轉(zhuǎn)移方程了:
f[0] = 0 (n=0) f[n] = min(f[n-1], f[n-5], f[n-11]) + 1 (n>0)那么我們?cè)倩氐竭@個(gè)找零問題中,這次我們假設(shè)給出不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回?-1。
比如輸入: coins = [1, 2, 5], amount = 11 輸出: 3 解釋: 11 = 5 + 5 + 1 復(fù)制代碼
其實(shí)上面的找零問題就是我們一直處理的找零問題的通用化,我們的面額是定死的,即1、5、11，這次是不定的，而是給了一個(gè)數(shù)組 coins 包含了相關(guān)的面值。
我們重新理一下思路：
- 確定最優(yōu)子結(jié)構(gòu): 最優(yōu)子結(jié)構(gòu)即原問題的解由子問題的最優(yōu)解構(gòu)成,我們假設(shè)最少需要k個(gè)硬幣湊足總面額n,那么f(n) = min{f(n-c?)}, c? 即是硬幣的面額。
- 處理邊界問題: 依然是老套路,當(dāng)n為負(fù)數(shù)的時(shí)候,值為正無窮大,當(dāng)n=0時(shí),值也為0.
- 得出動(dòng)態(tài)轉(zhuǎn)移方程:?f[0] = 0 (n=0) f[n] = min(f[n-c?]) + 1 (n>0)?
我們根據(jù)上面的推導(dǎo),得出以下代碼:
public int coinChange(int[] coins, int amount) {// 初始化備忘錄,用amount+1填滿備忘錄,amount+1 表示該值不可以用硬幣湊出來int[] dp = new int[amount + 1];Arrays.fill(dp,amount+1);// 設(shè)置初始條件為 0dp[0]=0;for (int coin : coins) {for (int i = coin; i <= amount; i++) {// 根據(jù)動(dòng)態(tài)轉(zhuǎn)移方程求出最小值if(coin <= i) {dp[i]=Math.min(dp[i],dp[i-coin]+1);}}}// 如果 `dp[amount] === amount+1`說明沒有最優(yōu)解返回-1,否則返回最優(yōu)解return dp[amount] == amount+1 ? -1 : dp[amount]; }7.小結(jié)
我們總結(jié)一下學(xué)習(xí)歷程：
其實(shí)動(dòng)態(tài)規(guī)劃本質(zhì)上就是被一再優(yōu)化過的暴力破解,我們通過動(dòng)態(tài)規(guī)劃減少了大量的重疊子問題,此后我們講到的所有動(dòng)態(tài)規(guī)劃題目的解題過程，都可以從暴力破解一步步優(yōu)化到動(dòng)態(tài)規(guī)劃。
可能你會(huì)問面試題這么多,到底哪一道應(yīng)該用動(dòng)態(tài)規(guī)劃?如何判斷?
其實(shí)最準(zhǔn)確的辦法就是看題目中的給定的問題，這個(gè)問題能不能被分解為子問題，再根據(jù)子問題的解是否可以得出原問題的解。
當(dāng)然上面的方法雖然準(zhǔn)確,但是需要一定的經(jīng)驗(yàn)積累,我們可以用一個(gè)雖然不那么準(zhǔn)確,但是足夠簡(jiǎn)單粗暴的辦法,如果題目滿足以下條件之一,那么它大概率是動(dòng)態(tài)規(guī)劃題目:
- 求最大值，最小值
- 判斷方案是否可行
- 統(tǒng)計(jì)方案?jìng)€(gè)數(shù)
參考文檔：
看一遍就理解：動(dòng)態(tài)規(guī)劃詳解
一文搞懂動(dòng)態(tài)規(guī)劃
總結(jié)
以上是生活随笔為你收集整理的【动态规划】不信看完你还不懂动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【LeetCode每周算法】零钱兑换
- 下一篇： 如何运行一个Java文件？