Burst Balloons

1public int maxCoins(int[] iNums) {
2    int[] nums = new int[iNums.length + 2];
3    int n = 1;
4    for (int x : iNums) nums[n++] = x;
5    nums[0] = nums[n++] = 1;
6
7    int[][] dp = new int[n][n];
8
9    // Process subproblems of increasing length
10    for (int length = 2; length < n; ++length) {
11        for (int left = 0; left < n - length; ++left) {
12            int right = left + length;
13            // Try each balloon as the last to burst
14            for (int i = left + 1; i < right; ++i) {
15                dp[left][right] = Math.max(dp[left][right],
16                    nums[left] * nums[i] * nums[right]
17                    + dp[left][i] + dp[i][right]);
18            }
19        }
20    }
21    return dp[0][n - 1];
22}