LeetCode Daily Problem P1039: Minimum Score of Polygon Triangulation

---

Timeline

Timeline

2025-09-29

init

Dynamic Programming

---

Problem:

P1039 Minimum Score of Polygon Triangulation

https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/?envType=daily-question&envId=2025-09-29

This problem clearly has subproblems, so we can consider dynamic programming. Suppose the vertices in the interval from i to j, where k is between i and j but not equal to i or j, then the problem equals the minimum triangulation score of the polygon from i to k plus the minimum triangulation score of the polygon from k to j plus the area of the triangle formed by i, j, k, because no matter how we partition, i and j must form a triangle with some vertex in the interval. From this we can write the state transition equation:

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

dp[i][j] represents the minimum triangulation score of the convex polygon from vertex i to vertex j, where k is any vertex in (i, j) excluding i and j

#include <climits>
#include <vector>
using std::vector;

class Solution {
    public:
        // dp[i][j]: the minimum triangulation score of the convex polygon from vertex i to vertex j
        // k is any vertex in (i, j), not including i and j
        // dp[i][j] =min k{ dp[i][k] + dp[k][j]+ values[i] *values[j] *values[k]}
        int minScoreTriangulation(vector<int> &values)
        {
                int vertex; // How many vertices are there from i to j?
                int i, j, k;
                int n;

                n = values.size();

                vector<vector<int> > dp(n, vector<int>(n, 0));

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