有?n?個氣球，編號為0?到?n - 1，每個氣球上都標有一個數字，這些數字存在數組?nums?中。

現(xiàn)在要求你戳破所有的氣球。戳破第?i?個氣球，你可以獲得?nums[i - 1] * nums[i] * nums[i + 1]?枚硬幣。?這里的?i - 1?和?i + 1?代表和?i?相鄰的兩個氣球的序號。如果?i - 1或?i + 1?超出了數組的邊界，那么就當它是一個數字為?1?的氣球。

求所能獲得硬幣的最大數量。

示例 1：

輸入：nums = [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

示例 2：

輸入：nums = [1,5]
輸出：10

提示：

?·n == nums.length

?·1 <= n <= 300

?·0 <= nums[i] <= 100

題目大意：在戳破一個氣球可獲得該氣球與周圍氣球乘積數的情況下計算最多可獲得的乘積數。

分析：

（1）在戳破一個氣球后會造成不相鄰的氣球變得相鄰，較難處理，因此考慮反向操作。將題目過程改為從兩個數字為1的氣球中不斷插入氣球，每次插入可獲得插入球與相鄰球的乘積數，計算最多可獲得的乘積數；

（2）通過（1）中方法將問題轉換為插入氣球的問題，由于是從兩個數字為1的氣球開始插入，因此在nums數組的首尾插入數字1，再設dp[l][r]為在區(qū)間（l，r）中的氣球全部插滿最多可獲得的硬幣數。若區(qū)間（l，r）中第一個氣球插入的位置為mid（l<mid<r），則dp[l][r]=dp[l][mid]+dp[mid][r]+nums[l]*nums[mid]*nums[r]。由此計算方式可得狀態(tài)轉移方程：

class Solution {
public:int maxCoins(vector<int>& nums) {nums.insert(nums.begin(),1);nums.emplace_back(1);int N=nums.size();vector<vector<int>> dp(N,vector<int>(N,0));for(int len=2,l,r,mid;len<N;++len){for(l=0,r=l+len;r<N;++l,++r){for(mid=l+1;mid<r;++mid){dp[l][r]=max(dp[l][r],dp[l][mid]+dp[mid][r]+nums[l]*nums[mid]*nums[r]);}}}return dp[0][N-1];}
};