經(jīng)典動(dòng)態(tài)規(guī)劃：戳氣球問(wèn)題

今天我們要聊的這道題「Burst Balloon」和之前我們寫(xiě)過(guò)的那篇 經(jīng)典動(dòng)態(tài)規(guī)劃：高樓扔雞蛋問(wèn)題 分析過(guò)的高樓扔雞蛋問(wèn)題類似，知名度很高，但難度確實(shí)也很大。因此 labuladong 公眾號(hào)就給這道題賜個(gè)座，來(lái)看一看這道題目到底有多難。

它是 LeetCode 第 312 題，題目如下：

title

首先必須要說(shuō)明，這個(gè)題目的狀態(tài)轉(zhuǎn)移方程真的比較巧妙，所以說(shuō)如果你看了題目之后完全沒(méi)有思路恰恰是正常的。雖然最優(yōu)答案不容易想出來(lái)，但基本的思路分析是我們應(yīng)該力求做到的。所以本文會(huì)先分析一下常規(guī)思路，然后再引入動(dòng)態(tài)規(guī)劃解法。

一、回溯思路

先來(lái)順一下解決這種問(wèn)題的套路：

我們前文多次強(qiáng)調(diào)過(guò)，很顯然只要涉及求最值，沒(méi)有任何奇技淫巧，一定是窮舉所有可能的結(jié)果，然后對(duì)比得出最值。

所以說(shuō)，只要遇到求最值的算法問(wèn)題，首先要思考的就是：如何窮舉出所有可能的結(jié)果？

窮舉主要有兩種算法，就是回溯算法和動(dòng)態(tài)規(guī)劃，前者就是暴力窮舉，而后者是根據(jù)狀態(tài)轉(zhuǎn)移方程推導(dǎo)「狀態(tài)」。

如何將我們的扎氣球問(wèn)題轉(zhuǎn)化成回溯算法呢？這個(gè)應(yīng)該不難想到的，我們其實(shí)就是想窮舉戳氣球的順序，不同的戳氣球順序可能得到不同的分?jǐn)?shù)，我們需要把所有可能的分?jǐn)?shù)中最高的那個(gè)找出來(lái)，對(duì)吧。

那么，這不就是一個(gè)「全排列」問(wèn)題嘛，我們前文 回溯算法框架套路詳解 中有全排列算法的詳解和代碼，其實(shí)只要稍微改一下邏輯即可，偽碼思路如下：

intres=Integer.MIN_VALUE; /*輸入一組氣球，返回戳破它們獲得的最大分?jǐn)?shù)*/ intmaxCoins(int[]nums){ backtrack(nums,0); returnres; } /*回溯算法的偽碼解法*/ voidbacktrack(int[]nums,intsocre){ if(nums為空){ res=max(res,score); return; } for(inti=0;i

回溯算法就是這么簡(jiǎn)單粗暴，但是相應(yīng)的，算法的效率非常低。這個(gè)解法等同于全排列，所以時(shí)間復(fù)雜度是階乘級(jí)別，非常高，題目說(shuō)了nums的大小n最多為 500，所以回溯算法肯定是不能通過(guò)所有測(cè)試用例的。

二、動(dòng)態(tài)規(guī)劃思路

這個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題和我們之前的動(dòng)態(tài)規(guī)劃系列文章相比有什么特別之處？為什么它比較難呢？

原因在于，這個(gè)問(wèn)題中我們每戳破一個(gè)氣球nums[i]，得到的分?jǐn)?shù)和該氣球相鄰的氣球nums[i-1]和nums[i+1]是有相關(guān)性的。

我們前文動(dòng)態(tài)規(guī)劃套路框架詳解 說(shuō)過(guò)運(yùn)用動(dòng)態(tài)規(guī)劃算法的一個(gè)重要條件：子問(wèn)題必須獨(dú)立。所以對(duì)于這個(gè)戳氣球問(wèn)題，如果想用動(dòng)態(tài)規(guī)劃，必須巧妙地定義dp數(shù)組的含義，避免子問(wèn)題產(chǎn)生相關(guān)性，才能推出合理的狀態(tài)轉(zhuǎn)移方程。

如何定義dp數(shù)組呢，這里需要對(duì)問(wèn)題進(jìn)行一個(gè)簡(jiǎn)單地轉(zhuǎn)化。題目說(shuō)可以認(rèn)為nums[-1] = nums[n] = 1，那么我們先直接把這兩個(gè)邊界加進(jìn)去，形成一個(gè)新的數(shù)組points：

intmaxCoins(int[]nums){ intn=nums.length; //兩端加入兩個(gè)虛擬氣球 int[]points=newint[n+2]; points[0]=points[n+1]=1; for(inti=1;i<=?n;?i++)?{ ????????points[i]?=?nums[i?-?1]; ????} ????//?... }

現(xiàn)在氣球的索引變成了從1到n，points[0]和points[n+1]可以認(rèn)為是兩個(gè)「虛擬氣球」。

那么我們可以改變問(wèn)題：在一排氣球points中，請(qǐng)你戳破氣球0和氣球n+1之間的所有氣球（不包括0和n+1），使得最終只剩下氣球0和氣球n+1兩個(gè)氣球，最多能夠得到多少分？

現(xiàn)在可以定義dp數(shù)組的含義：

dp[i][j] = x表示，戳破氣球i和氣球j之間（開(kāi)區(qū)間，不包括i和j）的所有氣球，可以獲得的最高分?jǐn)?shù)為x。

那么根據(jù)這個(gè)定義，題目要求的結(jié)果就是dp[0][n+1]的值，而 base case 就是dp[i][j] = 0，其中0 <= i <= n+1, j <= i+1，因?yàn)檫@種情況下，開(kāi)區(qū)間(i, j)中間根本沒(méi)有氣球可以戳。

//basecase已經(jīng)都被初始化為0 int[][]dp=newint[n+2][n+2];

現(xiàn)在我們要根據(jù)這個(gè)dp數(shù)組來(lái)推導(dǎo)狀態(tài)轉(zhuǎn)移方程了，根據(jù)我們前文的套路，所謂的推導(dǎo)「狀態(tài)轉(zhuǎn)移方程」，實(shí)際上就是在思考怎么「做選擇」，也就是這道題目最有技巧的部分：

不就是想求戳破氣球i和氣球j之間的最高分?jǐn)?shù)嗎，如果「正向思考」，就只能寫(xiě)出前文的回溯算法；我們需要「反向思考」，想一想氣球i和氣球j之間最后一個(gè)被戳破的氣球可能是哪一個(gè)？

其實(shí)氣球i和氣球j之間的所有氣球都可能是最后被戳破的那一個(gè)，不防假設(shè)為k?；仡檮?dòng)態(tài)規(guī)劃的套路，這里其實(shí)已經(jīng)找到了「狀態(tài)」和「選擇」：i和j就是兩個(gè)「狀態(tài)」，最后戳破的那個(gè)氣球k就是「選擇」。

根據(jù)剛才對(duì)dp數(shù)組的定義，如果最后一個(gè)戳破氣球k，dp[i][j]的值應(yīng)該為：

dp[i][j]=dp[i][k]+dp[k][j] +points[i]*points[k]*points[j]

你不是要最后戳破氣球k嗎？那得先把開(kāi)區(qū)間(i, k)的氣球都戳破，再把開(kāi)區(qū)間(k, j)的氣球都戳破；最后剩下的氣球k，相鄰的就是氣球i和氣球j，這時(shí)候戳破k的話得到的分?jǐn)?shù)就是points[i]*points[k]*points[j]。

那么戳破開(kāi)區(qū)間(i, k)和開(kāi)區(qū)間(k, j)的氣球最多能得到的分?jǐn)?shù)是多少呢？嘿嘿，就是dp[i][k]和dp[k][j]，這恰好就是我們對(duì)dp數(shù)組的定義嘛！

結(jié)合這個(gè)圖，就能體會(huì)出dp數(shù)組定義的巧妙了。由于是開(kāi)區(qū)間，dp[i][k]和dp[k][j]不會(huì)影響氣球k；而戳破氣球k時(shí)，旁邊相鄰的就是氣球i和氣球j了，最后還會(huì)剩下氣球i和氣球j，這也恰好滿足了dp數(shù)組開(kāi)區(qū)間的定義。

那么，對(duì)于一組給定的i和j，我們只要窮舉i < k < j的所有氣球k，選擇得分最高的作為dp[i][j]的值即可，這也就是狀態(tài)轉(zhuǎn)移方程：

//最后戳破的氣球是哪個(gè)？ for(intk=i+1;k

寫(xiě)出狀態(tài)轉(zhuǎn)移方程就完成這道題的一大半了，但是還有問(wèn)題：對(duì)于k的窮舉僅僅是在做「選擇」，但是應(yīng)該如何窮舉「狀態(tài)」i和j呢？

for(inti=...;;) for(intj=...;;) for(intk=i+1;k

三、寫(xiě)出代碼

關(guān)于「狀態(tài)」的窮舉，最重要的一點(diǎn)就是：狀態(tài)轉(zhuǎn)移所依賴的狀態(tài)必須被提前計(jì)算出來(lái)。

拿這道題舉例，dp[i][j]所依賴的狀態(tài)是dp[i][k]和dp[k][j]，那么我們必須保證：在計(jì)算dp[i][j]時(shí)，dp[i][k]和dp[k][j]已經(jīng)被計(jì)算出來(lái)了（其中i < k < j）。

那么應(yīng)該如何安排i和j的遍歷順序，來(lái)提供上述的保證呢？我們前文 動(dòng)態(tài)規(guī)劃答疑篇 寫(xiě)過(guò)處理這種問(wèn)題的一個(gè)雞賊技巧：根據(jù) base case 和最終狀態(tài)進(jìn)行推導(dǎo)。

PS：最終狀態(tài)就是指題目要求的結(jié)果，對(duì)于這道題目也就是dp[0][n+1]。

我們先把 base case 和最終的狀態(tài)在 DP table 上畫(huà)出來(lái)：

對(duì)于任一dp[i][j]，我們希望所有dp[i][k]和dp[k][j]已經(jīng)被計(jì)算，畫(huà)在圖上就是這種情況：

那么，為了達(dá)到這個(gè)要求，可以有兩種遍歷方法，要么斜著遍歷，要么從下到上從左到右遍歷：

斜著遍歷有一點(diǎn)難寫(xiě)，所以一般我們就從下往上遍歷，下面看完整代碼：

intmaxCoins(int[]nums){ intn=nums.length; //添加兩側(cè)的虛擬氣球 int[]points=newint[n+2]; points[0]=points[n+1]=1; for(inti=1;i<=?n;?i++)?{ ????????points[i]?=?nums[i?-?1]; ????} ????//?base?case?已經(jīng)都被初始化為?0 ????int[][]?dp?=?new?int[n?+?2][n?+?2]; ????//?開(kāi)始狀態(tài)轉(zhuǎn)移 ????//?i?應(yīng)該從下往上 ????for?(int?i?=?n;?i?>=0;i--){ //j應(yīng)該從左往右 for(intj=i+1;j

至此，這道題目就完全解決了，十分巧妙，但也不是那么難，對(duì)吧？

關(guān)鍵在于dp數(shù)組的定義，需要避免子問(wèn)題互相影響，所以我們反向思考，將dp[i][j]的定義設(shè)為開(kāi)區(qū)間，考慮最后戳破的氣球是哪一個(gè)，以此構(gòu)建了狀態(tài)轉(zhuǎn)移方程。

對(duì)于如何窮舉「狀態(tài)」，我們使用了小技巧，通過(guò) base case 和最終狀態(tài)推導(dǎo)出i,j的遍歷方向，保證正確的狀態(tài)轉(zhuǎn)移。