Burst Balloons

题目
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.

答案
非常经典的区间型dp题目，值得好好学习
对于dp题目，

第一步先去思考最后一步是什么？
最后一步就是刺破0到n - 1中的某个气球，在最后一步的时候，我们只剩下一个气球，所以这个气球的左边adjacent气球其实是nums[-1] = 1, 右边adjacent气球是nums[n] = 1
解决了这个问题后，剩下的就是递归求解刺破左右两边区间气球各自的max cost了。
无论刺破左边还是刺破右边，都可以break down为与"最后一步"类似的子问题。

代码如下

class Solution {
    public int maxCoins(int[] nums) {
        int n =  nums.length;
        if(n == 0) return 0;
        int[] A = new int[n + 2];
        int[][] f = new int[n + 2][n + 2];
        // fake ballons        
        A[0] = A[n + 1] = 1;
        for(int i = 1; i <= n; i++) A[i] = nums[i - 1];
        
        // Base case: intervals of len = 2 has no ballons to burst
        for(int i = 0; i <= n; i++)
            f[i][i + 1] = 0;
        
        // Now n := length of f array
        n += 2;
        
        for(int len = 3; len <= n; len++) {
            for(int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                f[i][j] = Integer.MIN_VALUE;
                for(int k = i + 1; k < j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i][k] + f[k][j] + A[i] * A[k] * A[j]);
                }
            }
        }
        return f[0][n - 1];
    }
}