312. Burst Balloonshtml
https://www.cnblogs.com/grandyang/p/5006441.htmlspa
dp[i][j]表示打爆区间 [i,j] 中的全部气球能获得的最多金币。code
计算的顺序是按照区间长度递增的顺序进行计算,从i-j长度为1到i-j长度为n。htm
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)); for(int len = 1;len <= n;len++){ for(int i = 1;i <= n - len + 1;i++){ int j = i + len - 1; for(int k = i;k <= j;k++){ dp[i][j] = max(dp[i][j],nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j]); } } } return dp[1][n]; } };