【Burst|Burst Balloons】http://www.lintcode.com/en/problem/burst-balloons/
package com.LintCode.BurstBalloons;
public class Solution {
/*
* @param nums: A list of integer
* @return: An integer, maximum coins
*/
public int maxCoins(int[] nums) {
// write your code here
int m = nums.length + 2;
int[] arr = new int[m];
System.arraycopy(nums, 0, arr, 1, m - 2);
arr[0] = 1;
arr[m - 1] = 1;
int[][] dp = new int[m][m];
//表示从i到j的最大收益
for (int len = 1;
len < m - 1;
len++) {
for (int left = 1;
left + len - 1 < m - 1;
left++) {
int right = left + len - 1;
//k是最后一个破的。所以它的收益就是乘以左边界左边和右边界的右边
for (int k = left;
k <= right;
k++) {
dp[left][right] = Math.max(dp[left][right],
arr[left - 1] * arr[k] * arr[right + 1] + dp[left][k - 1] + dp[k + 1][right]);
}
}
}
return dp[1][m - 2];
}
}
