Minimum Score Triangulation of Polygon LeetCode solution in Java

1
class Solution {
2
  int solve(int[] v, int i, int j) {
3
    if (i + 1 == j) return 0;
4
    int ans = Integer.MAX_VALUE;
5
    for (int k = i + 1; k < j; k++) {
6
      ans = Math.min(ans, (v[i] * v[j] * v[k] + solve(v, i, k) + solve(v, k, j)));
7
    }
8
    return ans;
9
  }
10

11
  int solveMem(int[] v, int i, int j, int[][] dp) {
12
    if (i + 1 == j) return 0;
13

14
    if (dp[i][j] != -1) return dp[i][j];
15

16
    int ans = Integer.MAX_VALUE;
17

18
    for (int k = i + 1; k < j; k++) {
19
      ans = Math.min(ans, (v[i] * v[j] * v[k] + solveMem(v, i, k, dp) + solveMem(v, k, j, dp)));
20
    }
21
    dp[i][j] = ans;
22
    return dp[i][j];
23
  }
24

25
  int solveTab(int[] v) {
26
    int n = v.length;
27
    int[][] dp = new int[n][n];
28

29
    for (int i = n - 1; i >= 0; i--) {
30
      for (int j = i + 2; j < n; j++) {
31

32
        int ans = Integer.MAX_VALUE;
33
        for (int k = i + 1; k < j; k++) {
34
          ans = Math.min(ans, (v[i] * v[j] * v[k] + dp[i][k] + dp[k][j]));
35
        }
36
        dp[i][j] = ans;
37
      }
38
    }
39

40
    return dp[0][n - 1];
41
  }
42

43
  public int minScoreTriangulation(int[] values) {
44
    int n = values.length;
45
    // return solve(values, 0, n-1); // For Recursion
46

47
    /* int[][] dp= new int[n][n]; // For Top-Down DP(Memoisation)
48
    for(int[] row:dp){
49
        Arrays.fill(row,-1);
50
    }
51

52
    return solveMem(values,0,n-1,dp);
53
    */
54

55
    return solveTab(values); // For Bottom-Down DP(Tabulisation)
56
  }
57
}