[Java] O(n ^ 3) | Memoization | MCM variation
\npublic int maxCoins(int[] arr) {\n        return burstBalloons(arr, 0, arr.length - 1, new Integer[arr.length][arr.length]);\n    }\n    \n    private int bur
```\npublic int maxCoins(int[] arr) {\n        return burstBalloons(arr, 0, arr.length - 1, new Integer[arr.length][arr.length]);\n    }\n    \n    private int burstBalloons(int[] arr, int beg, int end, Integer[][] dp) {\n        if(beg < 0 || end < 0 || beg >= arr.length || end >= arr.length) return 0;\n        \n        if(dp[beg][end] != null) return dp[beg][end];\n        int max = 0;\n        int prev = beg - 1 >= 0 ? arr[beg - 1] : 1;\n        int next = end + 1 < arr.length ? arr[end + 1] : 1;\n        \n        for(int i = beg; i <= end; i++) {\n            max = Math.max(max, burstBalloons(arr, beg, i - 1, dp) + (prev * arr[i] * next) + burstBalloons(arr, i + 1, end, dp));\n        }\n        \n        return dp[beg][end] = max;\n    }\n```
['Dynamic Programming', 'Memoization', 'Java']