LeetCode 312. Burst Balloons

题目链接：https://leetcode.com/problems/burst-balloons/

题意：有n个气球，编号为0-n-1，第i个气球权重为num[i]，现在要将这所有的气球烧毁，烧毁第二个气球的代价为num[i-1]*num[i]*num[i+1]，且第i个气球烧毁后，第i-1个气球和第i+1个气球变为相邻的气球，问烧毁所有气球的最小代价为多少。假设num[-1]=num[n]=1,0<=n<=500,0<=num[i]<=100.

为了便方便，将气球编号设为0-n，则num[0]=num[n+1]=1。区间dp：dp[i][j]表示烧毁第i个和第j个之间的所有气球的最小代价（不包括气球i和j），则对于i和j之间的某个气球k，假设k是最后一个烧毁的，则可以推出dp方程：$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+num[i]*num[k]*num[j]), i<k<j,j-i>1$

由于i<k<j，因此i从n-1到0，j从i+2到n+1，枚举k即可。dp[0][n+1]即为答案

class Solution {
public:
	int maxCoins(vector<int>& nums) {
		int n = nums.size();
		nums.insert(nums.begin(), 1);   //nums[0]=nums[n+1]=1
		nums.push_back(1);
		int **dp = new int*[n + 2];
		for (int i = 0;i <= n + 1;i++) {
			dp[i] = new int[n + 2];
			memset(dp[i], 0, 4 * (n + 2));
		}
		for (int i = n-1;i >= 0;i--)
			for (int j = i + 2;j <= n + 1;j++) {
				if (j - i == 2)   //i,j,k恰好相邻
					dp[i][j] = nums[i] * nums[i + 1] * nums[j];
				if (j - i>2) {
					for (int k = i + 1;k<j;k++)  //k为ij中最后一个销毁的
						dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[k] * nums[i] * nums[j]);
				}
			}
		return dp[0][n+1];
	}
};