一篇學(xué)會(huì)理解動(dòng)態(tài)規(guī)劃
本文轉(zhuǎn)載自微信公眾號(hào)「神奇的程序員」，作者神奇的程序員。轉(zhuǎn)載本文請(qǐng)聯(lián)系神奇的程序員公眾號(hào)。
前言
動(dòng)態(tài)規(guī)劃是一種比較難以理解的算法思想，本文結(jié)合自己的理解采用通俗易懂的方式來(lái)講解下動(dòng)態(tài)規(guī)劃，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。
思路分析
接下來(lái)，我們通過(guò)一個(gè)例子來(lái)逐步分析，引出動(dòng)態(tài)規(guī)劃思想。
假設(shè)，你家里三種面值的鈔票(1元、5元、11元)無(wú)數(shù)張，現(xiàn)在需要用這些鈔票湊出某個(gè)金額出來(lái)，我們需要怎樣搭配才能用最少的鈔票數(shù)量湊出這個(gè)金額出來(lái)?
例如：我們要湊15元出來(lái)。
貪心思想 - 只顧眼前
依據(jù)我們的生活經(jīng)驗(yàn)，肯定是先用面紙較大的鈔票，用總金額做減法運(yùn)算，思路如下：
- 先拿1張11元的鈔票，接下來(lái)我們要湊的金額就是4元(15 - 11)
- 要湊4元出來(lái)，我們只能用1元鈔票來(lái)湊，我們需要4張1元紙幣(4 - 1 - 1 - 1 - 1)
15元湊出來(lái)了，我們總共用了5張鈔票(1張11元的，4張1元的)。這種策略，我們稱之為貪心，我們把要湊的金額設(shè)為w，需要用的鈔票面額設(shè)為m，貪心策略會(huì)盡快的讓w變的更小，每減少一次，我們接下來(lái)要面對(duì)的局面就是湊出w - m。
經(jīng)過(guò)我們大腦計(jì)算后，這種策略湊出15元所用的鈔票數(shù)量并不是最少的，我們直接使用3張5元的鈔票就可以湊這個(gè)金額。
更好的方案 - 動(dòng)態(tài)規(guī)劃
我們使用貪心思想來(lái)解決這個(gè)問(wèn)題時(shí)，只考慮了眼前的情況，格局小了，那么我們現(xiàn)在應(yīng)該如何避免這種情況呢?
如果使用暴力枚舉的方法來(lái)湊出金額，明顯時(shí)間復(fù)雜度過(guò)高，太多種組合方式可以湊出這個(gè)金額了，枚舉它們的時(shí)間是不可承受的。
重疊子問(wèn)題
接下來(lái)，我們來(lái)嘗試著，找一下這個(gè)問(wèn)題的性質(zhì)。
- 一開(kāi)始，如果我們?nèi)×嗣嬷禐?1的鈔票，那么接下來(lái)面臨的問(wèn)題就是湊出金額為4時(shí)所需的最少鈔票數(shù)量
- 一開(kāi)始，如果我們?nèi)×嗣嬷禐?的鈔票，那么接下來(lái)面臨的問(wèn)題就是湊出金額為10時(shí)所需的最少鈔票數(shù)量
- 一開(kāi)始，如果我們?nèi)×嗣嬷禐?的鈔票，那么接下來(lái)面臨的問(wèn)題就是湊出金額為14時(shí)所需的最少鈔票數(shù)量
經(jīng)過(guò)上述分析，我們會(huì)發(fā)現(xiàn)這些問(wèn)題都有一個(gè)共同的形式：給定一個(gè)金額，湊出這個(gè)金額所需的最少鈔票數(shù)量。
我們將一個(gè)大問(wèn)題拆解成了三個(gè)子問(wèn)題。
接下來(lái)，我們?cè)賮?lái)分析下這三個(gè)子問(wèn)題，我們用f(n)來(lái)表示湊出n所需的最少鈔票數(shù)量，用cost來(lái)表示湊出w所需的鈔票數(shù)量，那么：
如果我們?nèi)×?1，最后用掉的鈔票總數(shù)就為：cost = f(4) + 1
如果我們?nèi)×?，最后用掉的鈔票總數(shù)就為：cost = f(10) + 1
如果我們?nèi)×?，最后用掉的鈔票總數(shù)就為：cost = f(14) + 1
觀察上述問(wèn)題后，我們會(huì)發(fā)現(xiàn)一個(gè)共同點(diǎn)：每取一個(gè)面值的鈔票，都需要計(jì)算剩余金額所需的最少鈔票數(shù)，而它們的計(jì)算方法都是相同的。
這三個(gè)子問(wèn)題都需要用同一種方式求解，那么它們就屬于重疊子問(wèn)題。
最優(yōu)子結(jié)構(gòu)
當(dāng)我們要湊出15元的金額時(shí)，我們需要的鈔票總數(shù)就為上述三種情況里所需鈔票數(shù)量最少的那一個(gè)。
我們?cè)谇骹(n)時(shí)，又要算出金額為n時(shí)所需的最少鈔票數(shù)，例如f(10)，我們只能用2種面值的鈔票(5元的和1元的)
如果用5元來(lái)湊的話，我們需要的鈔票數(shù)就為：f(5) + 1
如果用1元來(lái)湊的話，我們需要的鈔票數(shù)就為：f(9) + 1
我們?cè)谇骹(n)時(shí)，一定會(huì)從其子問(wèn)題的解決方案中找出所需硬幣數(shù)量最少的那個(gè)，即：
f(n) = min(f(n - 1), f(n -5 ), f(n - 11)) + 1
大問(wèn)題的最優(yōu)解可以由子問(wèn)題的最優(yōu)解推出，這個(gè)性質(zhì)就稱為最優(yōu)子結(jié)構(gòu)。
無(wú)后效性
通過(guò)上面的分析，我們知道了金額為15時(shí)，需要求出3個(gè)重疊子問(wèn)題的解，選出最優(yōu)的那個(gè)就是最終問(wèn)題的解。
那三個(gè)子問(wèn)題又有自己的重疊子問(wèn)題，我們?cè)谇蠼膺@些重疊子問(wèn)題時(shí)，只需要知道最終答案，不用去關(guān)心他們是如何算出來(lái)的，因?yàn)樗麄兊挠?jì)算過(guò)程并不會(huì)對(duì)之后的問(wèn)題產(chǎn)生影響。
例如：f(4), f(10), f(14) ，我們只需要求出他們的具體值，他們的計(jì)算過(guò)程對(duì)我們之后要求解的問(wèn)題沒(méi)有影響。
如果給定某一階段的狀態(tài)，這一階段以后過(guò)程的發(fā)展，不受這階段以前各段狀態(tài)的影響，就稱為無(wú)后效性，即：未來(lái)與過(guò)去無(wú)關(guān)。
剪繩子
有一根長(zhǎng)度為n的繩子，把繩子剪成m段(m、n都是整數(shù)，n > 1并且m > 1)，每段繩子的長(zhǎng)度記為k[0], k[1], ..., k[m]。
請(qǐng)問(wèn)k[m] * k[1] * ... * k[m]可能的最大乘積是多少?
例如：當(dāng)繩子長(zhǎng)度為8時(shí)，我們把它剪成長(zhǎng)度分別為2、3、3的三段，此時(shí)得到的最大乘積是18。
思路分析
接下來(lái)，我們來(lái)分析這個(gè)例子，看看能否用動(dòng)態(tài)規(guī)劃來(lái)解決。
根據(jù)題意，我們可知下述信息：
- 繩子的長(zhǎng)度肯定大于1且每次至少切一刀
- 我們用f(n)來(lái)表示長(zhǎng)度為n的繩子所有切法的最大乘積
那么，當(dāng)繩子的長(zhǎng)度為2時(shí)，我們只有一種切法，從中間切，這條繩子會(huì)被切為長(zhǎng)度各為1的兩小段，如下圖所示：
當(dāng)n=2時(shí)，f(n) = 1 * 1 = 1，即：f(2) = 1
我們繼續(xù)分析n=3的情況，如下圖所示，它有2種切法
- 切成長(zhǎng)度為1和長(zhǎng)度為2的兩小段
- 切成長(zhǎng)度分別為1、1、1的三小段
從切法2中，我們可以看出它其實(shí)就是對(duì)長(zhǎng)度為2的繩子進(jìn)行了一次切分，經(jīng)過(guò)前面的分析，我們已經(jīng)知道了它的所有切法的最大乘積是1，那么他們的乘積就是1 * 1 * 1 = 1。
因此， 我們不對(duì)他進(jìn)行劃分，直接取切法1的乘積，即: f(3) = 2
我們?cè)賮?lái)看下n=4的情況，如下圖所示，它有3種切法
- 切成長(zhǎng)度為1和長(zhǎng)度為3的兩小段
- 切成長(zhǎng)度為2和長(zhǎng)度為2的兩小段
- 切長(zhǎng)度為別為1的四小段
從切法1中，我們可以看出長(zhǎng)度為3的那一段繩子的最大乘積我們已經(jīng)算出來(lái)了(f(3) = 2)，如果我們對(duì)這段繩子進(jìn)行切分的話，乘積就變小了，所以我們選擇不切分這部分繩子，那么切法1的最大乘積就為1 * 3 = 3。
從切法2中，我們可以看出那兩段繩子的長(zhǎng)度都為2，而長(zhǎng)度為2的繩子的最大乘積我們也已經(jīng)算出來(lái)了(f(2) = 1)，如果切分的話，乘積就變小了，那么切法2的最大乘積就為2 * 2 = 4。
綜上所述，我們可以發(fā)現(xiàn)這樣一條規(guī)律：
- 無(wú)論繩子最終被切成多少段，它肯定是一刀一刀來(lái)切分的
- 繩子長(zhǎng)度為2或者3時(shí)，不會(huì)再進(jìn)行切分了，直接取其長(zhǎng)度
那么，對(duì)于一條繩子來(lái)說(shuō)，它一旦被切了一刀，就會(huì)被劃分為2個(gè)子問(wèn)題：
- 切割點(diǎn)左側(cè)的繩子怎么切
- 切割點(diǎn)右側(cè)的繩子怎么切
因?yàn)槲覀兪菑?開(kāi)始往后推的，前面的繩子怎么切，我們已經(jīng)存起來(lái)了。
分析到這里，我們發(fā)現(xiàn)它已經(jīng)滿足動(dòng)態(tài)規(guī)劃的2個(gè)特性了：
- 重疊子問(wèn)題：繩子被切開(kāi)后，每一部分的繩子還可能再繼續(xù)進(jìn)行切分，每次切分要面臨的子問(wèn)題都是一樣的
- 最優(yōu)子結(jié)構(gòu)：對(duì)每部分的繩子進(jìn)行切分時(shí)，我們都需要求出這部分繩子的所有切法中最大乘積是多少，滿足了最優(yōu)子結(jié)構(gòu)這個(gè)特性
我們?cè)賮?lái)分析下n=5的情況，如下圖所示，我們的第一刀有兩種切法：從1位置、從2位置切，分別可以將繩子切為：
- 長(zhǎng)度為1和長(zhǎng)度為4的兩小段
- 長(zhǎng)度為2和長(zhǎng)度為3的兩小段
我們用一個(gè)數(shù)組(result)將前面已經(jīng)求出來(lái)的繩子的最大乘積(最優(yōu)解)存起來(lái)，綜上所述，我們知道了當(dāng)繩子長(zhǎng)度小于4時(shí)，每段繩子長(zhǎng)度的最大乘積是固定的，即：
- result[0] = 0
- result[1] = 1
- result[2] = 2
- result[3] = 3
注意：因?yàn)槔K子至少要切一刀且繩子的長(zhǎng)度大于1，所以當(dāng)繩子長(zhǎng)度為1時(shí)是沒(méi)法進(jìn)行裁切的，因此它的最大乘積為1。
當(dāng)繩子長(zhǎng)度為2或3時(shí)，我們不會(huì)對(duì)它進(jìn)行切分，因此他們的最大乘積就是其本身的長(zhǎng)度。
觀察上圖后我們發(fā)現(xiàn)，當(dāng)繩子長(zhǎng)度大于等于4時(shí)，第一刀要的位置切法最多只能切到繩子長(zhǎng)度一半的位置，每次切分出來(lái)的子問(wèn)題，我們?cè)谇懊嬉呀?jīng)算過(guò)并且放進(jìn)了result中，我們只需將每種切法的子問(wèn)題最優(yōu)解相乘取出最大值即可。
當(dāng)n=4時(shí)，第一刀可以切的位置可以是：1、2：
- result[4] = max(result[1] * result[3], result[2] * result[2])
- = max(1 * 3, 2 * 2)
- = max(3, 4)
- = 4
當(dāng)n=5時(shí)，第一刀可以切的位置可以是：1、2：
- result[5] = max(result[1] * result[4], result[2] * result[3])
- = max(1 * 4, 2 * 3 )
- = max(4, 6)
- = 6
當(dāng)n = 6時(shí)，第一刀可以切的位置可以是：1、2、3
- result[6] = max(result[1] * result[5], result[2] * result[4], result[3] * result[3])
- = max(1 * 6, 2 * 4, 3 * 3)
- = max(6, 8, 9)
- = 9
研究到這里，我們會(huì)發(fā)現(xiàn)在求子問(wèn)題的最優(yōu)解時(shí)，我們只關(guān)心它的結(jié)果，它的計(jì)算過(guò)程并不會(huì)影響到我們最終問(wèn)題的解，那么它也滿足了動(dòng)態(tài)規(guī)劃的最后一個(gè)性質(zhì)：無(wú)后效性
遞推公式
經(jīng)過(guò)上面的一系列的推導(dǎo)，我們發(fā)現(xiàn)這個(gè)問(wèn)題已經(jīng)滿足了動(dòng)態(tài)規(guī)劃的三個(gè)性質(zhì)，那么也就是說(shuō)這個(gè)問(wèn)題是可以用動(dòng)態(tài)規(guī)劃來(lái)解決的。
經(jīng)過(guò)上面的分析，我們知道了不管怎么切，繩子都會(huì)被切成兩部分，然后再分別求解這兩部分的最大乘積，那么當(dāng)繩子長(zhǎng)度為n時(shí)，我們就能得到如下所示的公式：
- result[n] = result[i] * result[n - i]
n為當(dāng)前要求的繩子長(zhǎng)度，i為當(dāng)前要切割位置。
繩子的不管從哪個(gè)位置切，都會(huì)被切成兩段，我們求出這兩段的乘積，求出每種切法的最大乘積就是長(zhǎng)度為n的繩子的最大乘積。
實(shí)現(xiàn)代碼
經(jīng)過(guò)上面的一系列分析，我們已經(jīng)徹底掌握了這道題的解法，思路有了，我們就可以用代碼將其實(shí)現(xiàn)了，如下所示(TypeScript代碼)：
- public cutTheRope(length: number): number {
- // 由于繩子只能整數(shù)切，所以繩子長(zhǎng)度小于2時(shí)，無(wú)法進(jìn)行裁剪
- if (length < 2) {
- return 0;
- }
- // 繩子長(zhǎng)度為2時(shí)，只能從中間裁剪, 所有切法的最大乘積為1
- if (length === 2) {
- return 1;
- }
- // 繩子長(zhǎng)度為3時(shí)，可以切成:
- // 1. 1 1 1
- // 2. 1 2
- // 1 * 2 > 1 * 1 * 1, 故長(zhǎng)度為3時(shí), 所有切法的最大乘積為2
- if (length === 3) {
- return 2;
- }
- // 創(chuàng)建結(jié)果數(shù)組，存儲(chǔ)每段長(zhǎng)度繩子切分時(shí)的最大乘積
- const products = new Array<number>(length + 1);
- // 長(zhǎng)度小于4時(shí)，繩子的最大乘積我們已經(jīng)推算出來(lái)了，因此直接保存即可
- products[0] = 0;
- products[1] = 1;
- // 繩子長(zhǎng)度為2或3時(shí)，不進(jìn)行拆分，最大乘積為繩子的長(zhǎng)度
- products[2] = 2;
- products[3] = 3;
- // 繩子長(zhǎng)度大于4時(shí)需要對(duì)繩子進(jìn)行切分，求出切分后的每段繩子的最大乘積
- for (let i = 4; i <= length; i++) {
- // 賦初始值
- products[i] = 0;
- // 當(dāng)前長(zhǎng)度繩子的最大乘積
- let max = 0;
- // 至少切一刀，從繩子的1位置開(kāi)始切，切到i/2位置。
- // 求出長(zhǎng)度為i時(shí)，切一刀后兩段繩子的最大乘積
- for (let j = 1; j <= i / 2; j++) {
- // 根據(jù)遞推公式求當(dāng)前裁剪位置的兩段繩子的乘積
- const product = products[j] * products[i - j];
- // 比對(duì)歷史切法中兩段繩子的最大乘積和當(dāng)前切法兩段繩子的乘積
- if (max < product) {
- // 替換最大值
- max = product;
- }
- // 修改當(dāng)前繩子長(zhǎng)度切法的最大乘積
- products[i] = max;
- }
- }
- // 每種長(zhǎng)度繩子的最大乘積都已經(jīng)求出，length位置的值就是整個(gè)問(wèn)題的解
- return products[length];
- }
完整代碼請(qǐng)移步：DynamicProgramming.ts[1]
編寫測(cè)試用例
我們將題目中求長(zhǎng)度為8的繩子帶入帶入上述代碼中，求出最大值來(lái)驗(yàn)證下我們的代碼是否是正確的，如下所示：
- import DynamicProgramming from "../DynamicProgramming.ts";
- const dynamicProgrammingTest = new DynamicProgramming();
- const maxVal = dynamicProgrammingTest.cutTheRope(8);
- console.log("最大值為", maxVal);
完整代碼請(qǐng)移步：DynamicProgramming-test.ts[2]
運(yùn)行結(jié)果如下：
同類型例子
當(dāng)你讀完本文后，相信你對(duì)動(dòng)態(tài)規(guī)劃已經(jīng)有了一定的理解，緊接著你可以嘗試的做一下其他能用動(dòng)態(tài)規(guī)劃解決的問(wèn)題，加深下理解，達(dá)到徹底掌握的目的。
我還寫了其他幾個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題的分析文章，如果你對(duì)此感興趣，請(qǐng)移步：
- 最少硬幣找零問(wèn)題[3]
- 背包問(wèn)題[4]
- 最長(zhǎng)公共子序列[5]
- 矩陣鏈相乘[6]
寫在最后
至此，文章就分享完畢了。
我是神奇的程序員，一位前端開(kāi)發(fā)工程師。
公眾號(hào)無(wú)法外鏈，如果文中有鏈接，可點(diǎn)擊下方閱讀原文查看??
參考資料
[1]DynamicProgramming.ts: https://github.com/likaia/algorithm-practice/blob/a31acfe5c9b3acbf51c9383a09003611b64ea16b/src/DynamicProgramming.ts#L9
[2]DynamicProgramming-test.ts: https://github.com/likaia/algorithm-practice/blob/7fda8ff39d15ab7a4030bd998a63e1ec331117c9/src/test-case/DynamicProgramming-test.ts
[3]最少硬幣找零問(wèn)題: https://juejin.cn/post/6869571836066299912#heading-7
[4]背包問(wèn)題: https://juejin.cn/post/6869571836066299912#heading-10
[5]最長(zhǎng)公共子序列: https://juejin.cn/post/6869571836066299912#heading-13
[6]矩陣鏈相乘: https://juejin.cn/post/6869571836066299912#heading-16
