Skip to content

← leetcode

Minimum Score Triangulation of Polygon

· Medium

LeetCode problem 1039

This question reads like a dynamic programming questio- do not ask me to elaborat-

The thought process for this question is we maintain n by n matrix called dp, where dp[a][b] represents the minimum triangulation score between vertex a and vertex b, where a < b. In the cases where a >= b, we simply have dp[a][b] = 0.

To generate the recursive solution, we will need to define more variables. If we let j be the starting vertex, and i be the difference between the starting and ending vertex, then dp[j][j+i] represents the minimum triangulation score between vertex j and vertex j+i.

To find this minimum triangulation score, there will always be a triangle formed with vertices j and j+i as its base. That implies that there exists a peak point, j+k such that 1 <= k <= i-1, and allows us to define the recursive equation:

dp[j][j+i] = min(dp[j][j+i],
                 dp[j][j+k] + (values[j] * values[j+k] * values[j+i]) + dp[j+k][j+i])

Therefore, we can formulate a triple-nested for loop to iterate through all possible states, before arriving at our answer dp[0][values.size()-1]:

for (int i = 3; i < values.size(); ++i) {
    for (int j = 0; j < values.size()-i; ++j) {
        dp[j][j+i] = INT32_MAX;
        for (int k = 1; k < i; ++k) {
            dp[j][j+i] = min(dp[j][j+i], dp[j][j+k] + dp[j+k][j+i] + (values[j] * values[j+k] * values[j+i]));
        }
    }
}

code

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        vector<vector<int>> dp (values.size(), vector<int>(values.size(), 0));

        for (int i = 0; i < values.size()-2; ++i) {
            dp[i][i+2] = values[i] * values[i+1] * values[i+2];
        }

        for (int i = 3; i < values.size(); ++i) {
            for (int j = 0; j < values.size()-i; ++j) {
                dp[j][j+i] = INT32_MAX;
                for (int k = 1; k < i; ++k) {
                    dp[j][j+i] = min(dp[j][j+i], dp[j][j+k] + dp[j+k][j+i] + (values[j] * values[j+k] * values[j+i]));
                }
            }
        }

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

complexity

  • Time: O(n^3) where n denotes the number of elements inside of values
  • Space: O(n^2)

time taken

  • 16 minutes and 34 seconds