Burst Balloons LeetCode solution in Java

1
class Solution {
2
  public int maxCoins(int[] nums) {
3
    int n = nums.length;
4

5
    //         adding 1 to the front and back
6
    int[] temp = new int[n + 2];
7
    temp[0] = 1;
8
    for (int i = 1; i < temp.length - 1; i++) {
9
      temp[i] = nums[i - 1];
10
    }
11
    temp[temp.length - 1] = 1;
12
    nums = temp;
13

14
    //         memoization
15
    int[][] dp = new int[n + 1][n + 1];
16
    for (int[] row : dp) {
17
      Arrays.fill(row, -1);
18
    }
19

20
    //         result
21
    return f(1, n, nums, dp);
22
  }
23

24
  int f(int i, int j, int[] a, int[][] dp) {
25
    if (i > j) return 0;
26
    if (dp[i][j] != -1) return dp[i][j];
27

28
    int max = Integer.MIN_VALUE;
29
    for (int n = i; n <= j; n++) {
30
      int coins = a[i - 1] * a[n] * a[j + 1] + f(i, n - 1, a, dp) + f(n + 1, j, a, dp);
31
      max = Math.max(max, coins);
32
    }
33
    return dp[i][j] = max;
34
  }
35
}
36

37
// Time Complexity: O(N * N * N) ~ O(N^3);
38
// Space Complexity: O(N^2) + O(N);