Skip to content

1039. Minimum Score Triangulation of Polygon 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int minScoreTriangulation(vector<int>& values) {
    const int n = values.size();
    vector<vector<int>> dp(n, vector<int>(n));

    for (int j = 2; j < n; ++j)
      for (int i = j - 2; i >= 0; --i) {
        dp[i][j] = INT_MAX;
        for (int k = i + 1; k < j; ++k)
          dp[i][j] =
              min(dp[i][j],
                  dp[i][k] + values[i] * values[k] * values[j] + dp[k][j]);
      }

    return dp[0][n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int minScoreTriangulation(int[] values) {
    final int n = values.length;
    int[][] dp = new int[n][n];

    for (int j = 2; j < n; ++j)
      for (int i = j - 2; i >= 0; --i) {
        dp[i][j] = Integer.MAX_VALUE;
        for (int k = i + 1; k < j; ++k)
          dp[i][j] = Math.min(dp[i][j], dp[i][k] + values[i] * values[k] * values[j] + dp[k][j]);
      }

    return dp[0][n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def minScoreTriangulation(self, values: list[int]) -> int:
    n = len(values)
    dp = [[0] * n for _ in range(n)]

    for j in range(2, n):
      for i in range(j - 2, -1, -1):
        dp[i][j] = math.inf
        for k in range(i + 1, j):
          dp[i][j] = min(dp[i][j], dp[i][k] + values[i]
                         * values[k] * values[j] + dp[k][j])

    return dp[0][n - 1]