1. 題目

有 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

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/burst-balloons
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. DP解題

看的別人的解題思路

• $dp[i][j]$ 表示戳破 i 到 j 的氣球獲得的最大金幣
• 每次戳破氣球的順序會影響后面的結果，直接求解的復雜度是$O(n!)$
• 逆向思考，假設最后戳破 k 號氣球，那么 k 號氣球左邊和右邊的求解是互不干擾的
• $dp[i][j]=max(dp[i][j],dp[i][k?1]+nums[i?1]?nums[k]?nums[j+1]+dp[k+1][j])$
• $[i,j]$ 有多少種組合呢，用他們的長度 $len$ 表示， $1<=len<=n$
• 在長度len下，i，j 窗口遍歷數組，在 i，j 窗口內用遞推公式求 $dp[i][j]$

class Solution { public:int maxCoins(vector<int>& nums) {int n = nums.size();nums.insert(nums.begin(),1);//首尾加入虛擬的氣球nums.push_back(1);vector<vector<int>> dp(n+2,vector<int>(n+2,0));int len, i, j, k;for(len = 1; len <= n; ++len) {for(i = 1; i <= n-len+1; ++i){j = len+i-1;for(k = i; k <= j; ++k){dp[i][j] = max(dp[i][j],dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1]);}}}return dp[1][n];} };

總結

以上是生活随笔為你收集整理的LeetCode 312. 戳气球（DP，难）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。