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

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

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

title

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

一、回溯思路

先來順一下解決這種問題的套路：

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

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

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

如何將我們的扎氣球問題轉(zhuǎn)化成回溯算法呢？這個應(yīng)該不難想到的，我們其實就是想窮舉戳氣球的順序，不同的戳氣球順序可能得到不同的分?jǐn)?shù)，我們需要把所有可能的分?jǐ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

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

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

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

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

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

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

intmaxCoins(int[]nums){ intn=nums.length; //兩端加入兩個虛擬氣球 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)為是兩個「虛擬氣球」。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、寫出代碼

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

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

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

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

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

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

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

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

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]; ????//?開始狀態(tài)轉(zhuǎn)移 ????//?i?應(yīng)該從下往上 ????for?(int?i?=?n;?i?>=0;i--){ //j應(yīng)該從左往右 for(intj=i+1;j

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

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

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