0312 Burst Balloons

312. Burst Balloons
     Hard

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
分析：直接用递归搜索解空间，将是n!的时间复杂度[首先从n个气球中选一个，然后从剩下的n-1个气球中选择一个，以此类推，也就是n*(n-1)*(n-2)...3*2*1]。
改进的方案：我们创建一个规模为size+2的数组，fullfbr[0]=fullfbr[size+1]=1, 真实的数据存到fullfbr[1]~fullfbr[size]. 假如只剩最后一个气球，index为pos，bgn(=1)，end(=size)，
[bgn,pos-1]的气球已经炸完，[pos+1,end]的气球也已经炸完，那么bgn-1 * pos * end+1 得到中间coin的值，左侧coin和右侧coin的值通过递归调用一样可以得到。

而用二维数组maxs记录计算过的结果，对于C语言来说没有动态数组，所以用动态分配内存实现动态数组，程序终于AC。

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

int getstore(int bgn, int end, int** maxs, int fnbr[]){
   int pos;
   int lcoin;
   int mcoin;
   int rcoin;
   int coin;
   if(bgn>end)return 0;
   if(maxs[bgn][end]!=-1)return maxs[bgn][end];
   pos = bgn;
   while(pos<=end){
      lcoin = getstore(bgn,pos-1,maxs,fnbr);
      //[bgn,pos-1],[pos+1,end] 这两段都已经炸完
      mcoin = fnbr[bgn-1] * fnbr[pos] * fnbr[end+1];
      rcoin = getstore(pos+1,end,maxs,fnbr);
      coin = lcoin+mcoin+rcoin;
      if(coin > maxs[bgn][end])
         maxs[bgn][end] = coin;
      pos+=1;
   }
   return maxs[bgn][end];
}

int maxCoins(int* nums, int size) {
   int i;
   int j;
   int *fullnbr = (int*)malloc(sizeof(int)*(size+2));
   fullnbr[0] = fullnbr[size+1] = 1;
   for(i=0; i<size; i++)
      fullnbr[i+1] = nums[i];
   
   size+=2;
   
   int **maxs = (int**)malloc(sizeof(int*)*size);
   for(i=0; i<size; i++){
      maxs[i] = (int*)malloc(sizeof(int)*size);
      for(j=i;j<size-1;j++)
         maxs[i][j] = -1;
   }
   return getstore(1,size-2,maxs,fullnbr);
}

int main(int argc, char* argv[])
{
   int a[]={3,1,5,8};
   int result;
   result = maxCoins(a,4);
   return 0;
}

这真是一个典型的动态规划题目，我对动态规划的理解有限，在我看来也就是记忆化搜索。

mcoin = fnbr[bgn-1] * fnbr[pos] * fnbr[end+1];

这句应该是最关键的一句。

附C++解法

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1, -1));
        vector<int> nums1(n + 2, 1);
        for (int i = 0; i < n; ++i) {
            nums1[i + 1] = nums[i];
        }
        return search(nums1, f, 1, n);
    }
private:
    int search(const vector<int>& nums, vector<vector<int>>& f, const int i, const int j) {
        if (i > j) {
            return 0;
        }
        if (f[i][j] >= 0) {
            return f[i][j];
        }
        for (int k = i; k <= j; ++k) {
            f[i][j] = max(f[i][j], search(nums, f, i, k - 1) + search(nums, f, k + 1, j) + nums[k] * nums[i - 1] * nums[j + 1]);
        }
        return f[i][j];
    }
};