LeetCode Solutions
1039. Minimum Score Triangulation of Polygon
Time: Space:
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];
}
};