Easiest Java Solution
The subproblems are overlapped. So we can use divide and conquer + cache.\n Balloons 0, 1, ..., n - 1\n What is the max value if we burst  all of them [0,  n - 
The subproblems are overlapped. So we can use divide and conquer + cache.\n* Balloons `0, 1, ..., n - 1`\n* What is the max value if we burst  all of them `[0,  n - 1]`?\n* Let's first consider bursting `[start, end]`\n* Imagine we burst index `i` at the end\n* `[start, ... i - 1, (i), i + 1 ... end]`\n* Before the end, we already bursted `[start, i - 1]` and `[i + 1, end]`\n* Before the end, boundaries `start - 1`, `i`, `end + 1` are always there\n* This helps us calculate coins without worrying about details inside `[start, i - 1]` and `[i + 1, end]`\n* So the range can be divided into\n* `start - 1`, `maxCoin(start, i - 1)`, `i`, `maxCoins(i + 1, end)`, `end + 1`\n\nHope it helps!\n\n    public int maxCoins(int[] nums) {\n        int[][] dp = new int[nums.length][nums.length];\n        return maxCoins(nums, 0, nums.length - 1, dp);\n    }\n    \n    public int maxCoins(int[] nums, int start, int end, int[][] dp) {\n        if (start > end) {\n            return 0;\n        }\n        if (dp[start][end] != 0) {\n            return dp[start][end];\n        }\n        int max = nums[start];\n        for (int i = start; i <= end; i++) {\n            int val = maxCoins(nums, start, i - 1, dp) + \n                      get(nums, i) * get(nums, start - 1) * get(nums, end + 1) + \n                      maxCoins(nums, i + 1, end, dp);\n                      \n            max = Math.max(max, val);\n        }\n        dp[start][end] = max;\n        return max;\n    }\n    \n    public int get(int[] nums, int i) {\n        if (i == -1 || i == nums.length) {\n            return 1;\n        }\n        return nums[i];\n    }
[]