leetcode312

 1 class Solution {
 2     public int maxCoins(int[] iNums) {
 3     int[] nums = new int[iNums.length + 2];
 4     int n = 1;
 5     for (int x : iNums) if (x > 0) nums[n++] = x;
 6     nums[0] = nums[n++] = 1;
 7 
 8 
 9     int[][] dp = new int[n][n];
10     for (int k = 2; k < n; ++k)
11         for (int left = 0; left < n - k; ++left) {
12             int right = left + k;
13             for (int i = left + 1; i < right; ++i)
14                 dp[left][right] = Math.max(dp[left][right], 
15                 nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
16         }
17 
18     return dp[0][n - 1];
19     }
20 }

参考：https://leetcode.com/problems/burst-balloons/discuss/76228/Share-some-analysis-and-explanations

补充一个python的实现：

 1 class Solution:
 2     def maxCoins(self, nums: 'List[int]') -> 'int':
 3         nums = [1] + nums + [1]
 4         n = len(nums)
 5         dp = [[0 for _ in range(n)]for _ in range(n)]
 6         for k in range(2,n):
 7             for left in range(n-k):
 8                 right = left + k
 9                 for i in range(left+1,right):
10                     dp[left][right] = max(dp[left][right],nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right])
11         return dp[0][n-1]