[LeetCode] 312. Burst Balloons

好难啊，不会做\(▔▽▔)/

	class Solution {
	public int maxCoins(int[] nums) {
	// dp[i][j] - max coins could get when burst all the balloons between i to j
	// dp[i][j] = max(dp[i][j], dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j]), i <= k <= j
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int[][] dp = new int[nums.length][nums.length];
	for (int len = 1; len <= nums.length; len++) {
	for (int i = 0; i + len <= nums.length; i++) {
	int j = i + len - 1;
	for (int k = i; k <= j; k++) {
	int left = i == 0 ? 1 : nums[i - 1];
	int right = j == nums.length - 1 ? 1 : nums[j + 1];
	int current = left * nums[k] * right;
	if (k - 1 >= i) {
	current = current + dp[i][k - 1];
	}
	if (k + 1 <= j) {
	current = current + dp[k + 1][j];
	}
	dp[i][j] = Math.max(dp[i][j], current);
	}
	}
	}
	return dp[0][nums.length - 1];
	}
	}

view raw maxCoins.java hosted with ❤ by GitHub