一看就是DP題，但是遞推公式比較難想。為了簡化問題，給 nums 開始和最后都加上1。

記 dp[i][j] 表示 nums[i~j] 能得到的最大coin。

k 表示保留著的氣球，

dp[i][j] = max_k { dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] + dp[k+1][j] }? i<=k<=j

dp 需要從小到大構(gòu)建，以 {1,1,2,3,1} 為例，dp[1][1], dp[2][2], dp[3][3], 然后再 dp[1][2], dp[2][3]，最后dp[1][3]

類似從小到大構(gòu)建的，常規(guī)方法是用一個(gè)變量l，然后枚舉i，用i和l計(jì)算出j，最后枚舉k。

class Solution { public:int maxCoins(vector<int>& nums) {int n=nums.size();nums.insert(nums.begin(),1);nums.push_back(1);// dp[i][j] - max coins from nums[i~j]vector<vector<int>> dp(n+2,vector<int>(n+2,0));for (int l=0;l<n;++l){for (int i=1;i<=n-l;++i){int j=i+l;for (int k=i;k<=j;++k){dp[i][j] = max(dp[i][j], dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]);}}}return dp[1][n];} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/hankunyan/p/11184515.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode 312. Burst Balloons的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。