312. Burst Balloons

47.79 %
class Solution {
    public int maxCoins(int[] nums) {
        // dp[i][j] -> maxCoins to burst from i to j
        // i <= k <= j, k is the last ballon to burst
        // dp[i][j] = dp[i, k - 1] + nums[k] + dp[k + 1, j]
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[][] dp = new int[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = j; i >= 0; i--) {
                if (i == j) {
                    dp[i][j] = nums[i] * (i - 1 >= 0 ? nums[i - 1] : 1)
                                       * (j + 1 < len ? nums[j + 1] : 1);
                } else {
                    int max = 0;
                    for (int k = i; k <= j; k++) {
                        int left = k - 1 < i ? 0 : dp[i][k - 1];
                        int right = k + 1 > j ? 0 : dp[k + 1][j];
                        max = Math.max(max, left + right + nums[k]
                                       * (i - 1 >= 0 ? nums[i - 1] : 1)
                                       * (j + 1 < len ? nums[j + 1] : 1));
                    }
                    dp[i][j] = max;
                }
            }
        }
        return dp[0][len - 1];
    }
}