312.Burst Balloons

https://leetcode.com/problems/burst-balloons/discuss/76228/

Java D&C with Memoization

class Solution {
    public int maxCoins(int[] originalNums) {
        int n = originalNums.length;
        int[] nums = new int[n + 2];
        nums[0] = 1;
        nums[n + 1] = 1;
        for(int i = 0, j = 1; i < n; i++, j++){
            nums[j] = originalNums[i];
        }

        //update n
        n = n + 2;
        //memo[i][j] burst from i+1 to j-1
        int[][] memo = new int[n][n];
        return burst(memo, nums, 0, n - 1);
    }

    public int burst(int[][] memo, int[] nums, int left, int right){
        if(left + 1 == right)
            return 0;
        if(memo[left][right] > 0)
            return memo[left][right];
        int ans = 0;
        for(int i = left + 1; i < right ; i++){
            ans = Math.max(ans, nums[left] * nums[i] * nums[right] + burst(memo, nums, left, i) + burst(memo, nums, i, right));
        }
        memo[left][right] = ans;
        return ans;
    }
}

2-DP-
class Solution {
    public int maxCoins(int[] originalNums) {
        int n = originalNums.length;
        int[] nums = new int[n + 2];
        nums[0] = 1;
        nums[n + 1] = 1;
        for(int i = 0, j = 1; i < n; i++, j++){
            nums[j] = originalNums[i];
        }

        //update n
        n = n + 2;
        //memo[i][j] burst from i+1 to j-1
        int[][] dp = new int[n][n];
        for(int k = 2; k < n; k++){
            for(int left = 0; left < n - k; left++){
                int right = left + k;
                for(int i = left + 1; i < right; i++){
                    dp[left][right] = Math.max(dp[left][right], nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right]);
                }
            }
        }
        return dp[0][n-1];
    }


}