0312. 戳氣球 · ttttt

# 0312. 戳氣球 ### 題目地址（312. 戳氣球） <https://leetcode-cn.com/problems/burst-balloons/> ### 題目描述 ``` <pre class="calibre18">``` 有 n 個氣球，編號為0 到 n-1，每個氣球上都標有一個數字，這些數字存在數組 nums 中。現在要求你戳破所有的氣球。每當你戳破一個氣球 i 時，你可以獲得 nums[left] * nums[i] * nums[right] 個硬幣。這里的 left 和 right 代表和 i 相鄰的兩個氣球的序號。注意當你戳破了氣球 i 后，氣球 left 和氣球 right 就變成了相鄰的氣球。求所能獲得硬幣的最大數量。說明: 你可以假設 nums[-1] = nums[n] = 1，但注意它們不是真實存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 示例: 輸入: [3,1,5,8] 輸出: 167 解釋: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167 ``` ``` ## 前置知識 - 回溯法 - 動態規劃 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路 #### 回溯法分析一下這道題，就是要戳破所有的氣球，獲得硬幣的最大數量，然后左右兩邊的氣球相鄰了。我的第一反應就是暴力，回溯法。但是肯定會超時，為什么呢？因為題目給的氣球數量有點多，最多 500 個；500 的階乘，會超時爆棧；但是我們依然寫一下代碼，找下突破口，小伙伴們千萬不要看不起暴力，暴力是優化的突破口；如果小伙伴對回溯法不太熟悉，我建議你記住下面的模版，也可以看我之前寫的文章，回溯法基本可以使用以下的模版寫。回溯法省心省力，0 智商負擔。 #### 代碼 ``` <pre class="calibre18">``` var maxCoins = function (nums) { let res = Number.MIN_VALUE; backtrack(nums, 0); return res; // 回溯法，狀態樹很大 function backtrack(nums, score) { if (nums.length == 0) { res = Math.max(res, score); return; } for (let i = 0, n = nums.length; i < n; i++) { let point = (i - 1 < 0 ? 1 : nums[i - 1]) * nums[i] * (i + 1 >= n ? 1 : nums[i + 1]); let tempNums = [].concat(nums); // 做選擇在 nums 中刪除元素 nums[i] nums.splice(i, 1); // 遞歸回溯 backtrack(nums, score + point); // 撤銷選擇 nums = [...tempNums]; } } }; ``` ``` #### 動態規劃回溯法的缺點也很明顯，復雜度很高，對應本題戳氣球；小伙伴們可以腦補一下執行過程的狀態樹，這里我偷個懶就不畫了；通過仔細觀察這個狀態樹，我們會發現這個狀態樹的【選擇】上，會有一些重復的選擇分支；很明顯存在了重復子問題；自然我就想到了能不能用動態規劃來解決；判讀能不能用動態規劃解決，還有一個問題，就是必須存在最優子結構；什么意思呢？其實就是根據局部最優，推導出答案；假設我們戳破第 k 個氣球是最優策略的最后一步，和上一步有沒有聯系呢？根據題目意思，戳破第 k 個，前一個和后一個就變成相鄰的了，看似是會有聯系，其實是沒有的。因為戳破第 k 個和 k-1 個是沒有聯系的，腦補一下回溯法的狀態樹就更加明確了；既然用動態規劃，那就老套路了，把動態規劃的三個問題想清楚定義好；然后找出題目的【狀態】和【選擇】，然后根據【狀態】枚舉，枚舉的過程中根據【選擇】計算遞推就能得到答案了。那本題的【選擇】是什么呢？就是戳哪一個氣球。那【狀態】呢？就是題目給的氣球數量。 1. 定義狀態 2. 這里有個細節，就是題目說明有兩個虛擬氣球，nums\[-1\] = nums\[n\] = 1；如果當前戳破的氣球是最后一個或者第一個，前面/后面沒有氣球了，不能乘以 0，而是乘以 1。 3. 定義狀態的最關鍵兩個點，往子問題（問題規模變小）想，最后一步最優策略是什么；我們假設最后戳破的氣球是 k，戳破 k 獲得最大數量的銀幣就是 nums\[i\] *nums\[k\]* nums\[j\] 再加上前面戳破的最大數量和后面的最大數量，即：nums\[i\] *nums\[k\]* nums\[j\] + 前面最大數量 + 后面最大數量，就是答案。 > 注意 i 不一定是 k - 1，同理 j 也不一定是 k + 1，因此可能 i - 1 和 i + 1 已經被戳破了。 - 而如果我們不考慮兩個虛擬氣球而直接定義狀態，戳到最后兩個氣球的時候又該怎么定義狀態來避免和前面的產生聯系呢？這兩個虛擬氣球就恰到好處了，這也是本題的一個難點之一。 - 那我們可以這樣來定義狀態，dp\[i\]\[j\] = x 表示戳破氣球 i 和氣球 j 之間（開區間，不包括 i 和 j）的所有氣球，可以獲得的最大硬幣數為 x。為什么開區間？因為不能和已經計算過的產生聯系，我們這樣定義之后，利用兩個虛擬氣球，戳到最后兩個氣球的時候就完美的避開了所有狀態的聯系。 - 狀態轉移方程 - 而對于 dp\[i\]\[j\]，i 和 j 之間會有很多氣球，到底該戳哪個先呢？我們直接設為 k，枚舉選擇最優的 k 就可以了。 - 1。 - 所以，最終的狀態轉移方程為：dp\[i\]\[j\] = max(dp\[i\]\[j\], dp\[i\]\[k\] + dp\[k\]\[j\] + nums\[k\] *nums\[i\]* nums\[j\])。由于是開區間，因此 k 為 i + 1, i + 2... j - 1。 - 初始值和邊界 - 由于我們利用了兩個虛擬氣球，邊界就是氣球數 n + 2 - 初始值，當 i == j 時，很明顯兩個之間沒有氣球，所有為 0； - 如何枚舉狀態 - 因為我們最終要求的答案是 dp\[0\]\[n + 1\]，就是戳破虛擬氣球之間的所有氣球獲得的最大值； - 當 i == j 時，i 和 j 之間是沒有氣球的，所以枚舉的狀態很明顯是 dp table 的左上部分，也就是 j 大于 i，如下圖所示，只給出一部分方便思考。 ![](https://img.kancloud.cn/cc/64/cc641c69c893745efc598b7041905a95_776x384.jpg)（圖有錯誤。圖中 dp\[k\]\[i\] 應該是 dp\[i\]\[k\]，dp\[j\]\[k\] 應該是 dp\[k\]\[j\]） > 從上圖可以看出，我們需要從下到上，從左到右進行遍歷。 #### 代碼代碼支持： JS, Python JS Code: ``` <pre class="calibre18">``` var maxCoins = function (nums) { let n = nums.length; // 添加兩側的虛擬氣球 let points = [1, ...nums, 1]; let dp = Array.from(Array(n + 2), () => Array(n + 2).fill(0)); // 最后一行開始遍歷,從下往上 for (let i = n; i >= 0; i--) { // 從左往右 for (let j = i + 1; j < n + 2; j++) { for (let k = i + 1; k < j; k++) { dp[i][j] = Math.max( dp[i][j], points[j] * points[k] * points[i] + dp[i][k] + dp[k][j] ); } } } return dp[0][n + 1]; }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def maxCoins(self, nums: List[int]) -> int: n = len(nums) points = [1] + nums + [1] dp = [[0] * (n + 2) for _ in range(n + 2)] for i in range(n, -1, -1): for j in range(i + 1, n + 2): for k in range(i + 1, j): dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]) return dp[0][-1] ``` ``` **復雜度分析** - 時間復雜度：O(N3)O(N ^ 3)O(N3) - 空間復雜度：O(N2)O(N ^ 2)O(N2) ### 總結簡單的 dp 題目會直接告訴你怎么定義狀態，告訴你怎么選擇計算，你只需要根據套路判斷一下能不能用 dp 解題即可，而判斷能不能，往往暴力就是突破口。而困難點的 dp，我覺的都是細節問題了，要注意的細節太多了。感覺力扣加加，路西法大佬，把我領進了動態規劃的大門，共勉。更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經30K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。