Java DP solution with expalination
For this problem, we firstly define a 2D dynamic programming table named OPT to represent the maximum coins we can get in the index range from left to right  de
For this problem, we firstly define a 2D dynamic programming table named `OPT` to represent the maximum coins we can get in the index range from `left` to `right`  denoted by `OPT[left, right]`. \n\nThen, we need to express this by some subproblems. The idea is to consider **which balloon is the last one to be bursted** so that we can get the maximum coins. Assume the last one bursted has index `i` with in `[left, right]`. In this way, our subproblems are the **maximum coins in both left side and right side of nums[k]**: values of `OPT[left, i-1]` and `OPT[i+1, right]`. Sum the results of these two subproblems and the coins from bursting last balloon to get `OPT[left, right]`.\n\nConcequently, our recurrence relation can be expressed as following\n```\nOPT[left, right] = max(OPT[left, right], OPT[left, i-1] + nums[left-1] * nums[i] * nums[right+1] + OPT[i+1, right])\n```\n\nNote that the index range we use here is inclusive.\n\n```\nclass Solution {\n    public int maxCoins(int[] inNums) {\n        int[] nums = new int[inNums.length + 2];\n        nums[0] = nums[nums.length - 1] = 1;\n        for(int i = 1; i < nums.length - 1; i++) {\n            nums[i] = inNums[i-1];\n        }\n        \n        int[][] DP = new int[nums.length][nums.length];\n        for(int size = 0; size < inNums.length; size++) {\n            for(int left = 1; left <= inNums.length - size; left++) {\n                int right = left + size;\n                for(int i = left; i <= right; i++) {\n                    DP[left][right] = Math.max(DP[left][right], nums[left-1] * nums[i] * nums[right+1] + DP[left][i-1] + DP[i+1][right]);\n                }\n            }\n        }\n        return DP[1][inNums.length];\n    }\n}\n```
[]