Skip to content

1039. Minimum Score Triangulation of Polygon 👍

  • Time:
  • Space:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int minScoreTriangulation(vector<int>& A) {
    vector<vector<int>> dp(A.size(), vector<int>(A.size(), 0));

    for (int j = 2; j < A.size(); ++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] + A[i] * A[k] * A[j] + dp[k][j]);
      }

    return dp[0][A.size() - 1];
  }
};