Givennballoons, indexed from0ton-1. Each balloon is painted with a number on it represented by arraynums. You are asked to burst all the balloons. If the you burst ballooniyou will getnums[left] * nums[i] * nums[right]coins. Hereleftandrightare adjacent indices ofi. After the burst, theleftandrightthen becomes adjacent.

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

Note:
(1) You may imaginenums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤n≤ 500, 0 ≤nums[i]≤ 100

Example:

Given[3, 1, 5, 8]

Return167

    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

Credits:
Special thanks to@dietpepsifor adding this problem and creating all test cases.

tag: DP, DFS, memorization

class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return dfs(nums, 0, nums.length - 1, new int[nums.length][nums.length]);
    }

    private int dfs(int[] nums, int start, int end, int[][] hash){
        if (start > end) return 0;
        if (hash[start][end] > 0) return hash[start][end];

        for (int i = start; i <= end; i++){
            hash[start][end] = Math.max(hash[start][end], (start - 1 == -1 ? 1 : nums[start - 1]) * nums[i] * (end + 1 == nums.length ? 1 : nums[end + 1]) + dfs(nums, start, i - 1, hash) + dfs(nums, i + 1, end, hash));
        }

        return hash[start][end];
    }
}