Problem

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.
- 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
Given [4, 1, 5, 10]
Return 270

nums = [4, 1, 5, 10] burst 1, get coins 4 * 1 * 5 = 20
nums = [4, 5, 10]    burst 5, get coins 4 * 5 * 10 = 200 
nums = [4, 10]       burst 4, get coins 1 * 4 * 10 = 40
nums = [10]          burst 10, get coins 1 * 10 * 1 = 10

Total coins 20 + 200 + 40 + 10 = 270

思路

• 和stone game开始一样, 先画搜索树, 因为任意一个气球都可以作为最后被打爆的气球, 如果定义剩下i个气球被打爆能达到最大值的话, 因为并没有规定气球要从头按某个顺序打爆, 所以我们并不知道剩下的这i个气球是在哪一个区间里面的i个气球(也就是说不知道头和尾在哪)
• 
• 所以我们将状态定义成
  • dp[i][j]: 代表第i个到第j个气球被打爆所获得的最大价值
  • size: n + 2; 因为dp[i][j]依赖于dp[i][i -1] 和 dp[j][j + 1], 所以需要两个额外的状态
• function
  • dp[i][j] = max(dp[i][k-1]+dp[k+1][j]+midvalue)
  • midValue = arr[i-1] * arr[k] * arr[j+1];
• initialize
  • for each i • dp[i][i] = arr[i-1] * arr[i] * arr[i+1];
  • 根据原数组num创建arr
    • arr[0] = 1
    • arr[1.....n] = num[0...n-1]
    • arr[n + 1] = 1
• answer
  • dp[1][n]

    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        boolean[][] visited = new boolean[n + 2][n + 2];
        int[][] dp = new int[n + 2][n + 2];
        int[] arr = new int[n + 2];

        for (int i = 0; i < n; i++) {
            arr[i + 1] = nums[i];
        }

        arr[0] = 1;
        arr[n + 1] = 1;

        return burstBalloons(arr, 1, n, dp, visited);
    }

    private int burstBalloons(int[] arr, int l, int r, int[][] dp, boolean[][] visited) {
        if (visited[l][r]) {
            return dp[l][r];
        }

        visited[l][r] = true;

        for (int k = l; k <= r; k++) {
            int coins = arr[l - 1] * arr[k] * arr[r + 1];
            int left = burstBalloons(arr, l, k - 1, dp, visited);
            int right = burstBalloons(arr, k + 1, r, dp, visited);
            dp[l][r] = Math.max(dp[l][r], left + right + coins);
        }

        return dp[l][r];
    }