1039. Minimum Score Triangulation of Polygon
Problem Description
You are given a convex, n
-sided polygon where the value of each vertex is provided as an integer array values
. The goal is to split this polygon into triangles, in a way that minimizes the total score of the triangulation. The total score is defined as the sum of the scores of each triangle, where the score of a triangle is calculated as the product of the values of its three vertices. The challenge lies in determining the best way to triangulate the polygon (i.e., how exactly to make the cuts to form triangles), such that the total score is as small as possible.
Intuition
The intuition behind solving this problem involves dynamic programming. Trying out each possible triangulation would be incredibly inefficient because it would involve an exponential number of combinations to check. Instead, dynamic programming allows us to break down the problem into smaller subproblems, remember (or cache) those solutions, and use them to build up a solution to the larger problem.
To apply dynamic programming, we look for a recurrence relation that expresses the solution to a problem in terms of the solutions to its subproblems. Here, we define dfs(i, j)
as the minimum score possible for triangulating the sub-polygon from vertex i
to vertex j
. To find dfs(i, j)
, we consider placing a triangle with one edge being the line segment from i
to j
, and the third vertex being k
, where i < k < j
. For each possible value of k
, dfs(i, j)
can then be recursively defined as the minimum of dfs(i, k) + dfs(k, j) + values[i] * values[k] * values[j]
.
The base case for this recursive function is when the sub-polygon has only two vertices (i + 1 == j)
; in this case, no triangle can be formed, and the score is 0.
To improve the efficiency of this algorithm, we use memoization, which is built into Python with the @cache
decorator. This stores the results of dfs
computations so that we don't have to recompute them when the same subproblems arise.
Thus, the solution to our problem is the value of dfs(0, len(values) - 1)
, which represents the minimum score possible for triangulating the entire polygon.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution leverages a design pattern known as dynamic programming. This programming paradigm solves complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.
The implementation starts by defining a function dfs(i, j)
which represents the minimum triangulation score that can be achieved within the vertices from i
to j
of the polygon. This function uses the memoization technique with the @cache
decorator to remember the results of previous computations, which is crucial for improving the performance of the solution.
In the dfs
function, there is a base case check:
- When
i + 1 == j
, it means there are only two vertices left, which cannot form a triangle. In this case, the score is0
.
For the recursive step:
- We loop through all possible third vertices
k
for the triangle, wherek
ranges fromi+1
toj-1
. - For each
k
, we calculate the score of the triangle formed by verticesi
,k
, andj
, which isvalues[i] * values[k] * values[j]
. - We add this score to the recursion of the remaining sub-polygon divided by this triangle, which results in two subproblems:
dfs(i, k)
anddfs(k, j)
representing the minimum score fromi
tok
and fromk
toj
, respectively. - The
min
function is applied to choose the smallest possible score amongst all combinations ofk
.
Thus, the function dfs
computes the desired triangulation score in a bottom-up manner, using previously stored results to calculate larger subproblems. The time complexity of this approach is O(n^3)
, where n
is the number of vertices in the polygon, as there are at most n
choices for i
and j
, and within each recursive call, we iterate over k
in a range of size at most n
.
Finally, the minimum score for the entire polygon can be obtained by calling dfs(0, len(values) - 1)
, which represents the minimum triangulation score from the first to the last vertex of the polygon.
The implementation of this algorithm uses no additional data structures apart from the given input and the internal caching mechanism provided by @cache
. The combination of recursion, memoization, and minimization at each step makes for an elegant and efficient solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example where our polygon has 4
vertices with the values array given as values = [1, 3, 1, 4]
. According to the problem, we aim to triangulate the polygon in such a way that the total score is as small as possible, where the score for each triangle is the product of its vertex values.
Starting with the function dfs(i, j)
:
-
We need to triangulate the polygon from vertex
0
to vertex3
, hence we calldfs(0, 3)
. -
Since
i + 1
does not equalj
, we proceed to find the minimum triangulation score.- We have two possibilities for vertex
k
as the third vertex for the triangle sincek
can be either1
or2
.
- We have two possibilities for vertex
-
For
k = 1
:- We calculate the score of the triangle
[0, 1, 3]
which is1 * 3 * 4 = 12
. - We then add this score to the score for the remaining sub-polygon formed by the vertices
0
to1
, and1
to3
. Here, the sub-polygon0-1
is just a line and does not form a triangle, sodfs(0, 1)
is0
, and we need to calculatedfs(1, 3)
. - Now, for
dfs(1, 3)
, we have only two points so again it does not form a triangle, resulting in score0
. - The total for
k = 1
is12 + 0 + 0 = 12
.
- We calculate the score of the triangle
-
For
k = 2
:- We calculate the score of the triangle
[0, 2, 3]
which is1 * 1 * 4 = 4
. - We again add this score to the score for the sub-polygon formed by vertices
0
to2
, and2
to3
. The sub-polygon2-3
is just a line, sodfs(2, 3)
is0
. - We need to calculate
dfs(0, 2)
. This is a triangle[0, 1, 2]
with a score1 * 3 * 1 = 3
. - So, the total for
k = 2
is4 + 3 + 0 = 7
.
- We calculate the score of the triangle
-
We select the minimum score for our two
k
options, which is7
, sodfs(0, 3)
returns7
.
Therefore, by recursively applying this approach using memoization to prevent redundant calculations, we determine that the minimum score for triangulating the polygon with vertices 1, 3, 1, 4
is 7
. The triangulation that yields this score is by slicing the polygon into triangles using vertices [0, 2, 3]
and [0, 1, 2]
.
Solution Implementation
1from functools import lru_cache # lru_cache is used since @cache is not defined
2
3class Solution:
4 def min_score_triangulation(self, values: List[int]) -> int:
5 """
6 Compute the minimum score of a triangulation of a polygon with 'values' vertices.
7
8 :param values: An array of scores associated with each vertex of the polygon.
9 :return: The minimum score of a triangulation.
10 """
11 @lru_cache(maxsize=None) # Adds memoization to reduce time complexity
12 def min_score(i: int, j: int) -> int:
13 """
14 Compute the minimum score by triangulating the polygon from vertex i to vertex j.
15
16 :param i: Start vertex index of the polygon part being considered.
17 :param j: End vertex index of the polygon part being considered.
18 :return: Minimum triangulation score for the vertices between i and j.
19 """
20 if i + 1 == j: # Base case: no polygon to triangulate if only two vertices
21 return 0
22
23 # Compute the minimum score by considering all possible triangulations
24 # between vertices 'i' and 'j', by choosing an intermediate vertex 'k'
25 # and adding the score formed by the triangle (i, k, j) plus the minimum
26 # triangulation scores for the polygons (i, ..., k) and (k, ..., j).
27 return min(
28 min_score(i, k) + min_score(k, j) + values[i] * values[k] * values[j]
29 for k in range(i + 1, j) # Iterate over all possible k between i and j
30 )
31
32 # Initiate the recursion with the full polygon from the first to the last vertex
33 return min_score(0, len(values) - 1)
34
35# Note: List and Tuple type hints should be imported from the typing module for this to work
36from typing import List
37
1class Solution {
2 private int numVertices;
3 private int[] vertexValues;
4 private Integer[][] memoization;
5
6 // Calculate the minimum score of triangulation for a polygon using given vertex values
7 public int minScoreTriangulation(int[] values) {
8 numVertices = values.length;
9 vertexValues = values;
10 memoization = new Integer[numVertices][numVertices];
11 return dfs(0, numVertices - 1);
12 }
13
14 // Depth-First Search helper method to recursively find the minimum score
15 private int dfs(int start, int end) {
16 // Base case: If the polygon has no area (two adjacent vertices), return 0
17 if (start + 1 == end) {
18 return 0;
19 }
20
21 // Check if the score has already been computed and cached
22 if (memoization[start][end] != null) {
23 return memoization[start][end];
24 }
25
26 // Initialize answer to a large number so any minimum can replace it
27 int minScore = Integer.MAX_VALUE;
28
29 // Iterate through all possible partitions of the polygon
30 for (int k = start + 1; k < end; ++k) {
31 // Recursively find the minimum score by considering the partition of the polygon
32 // into a triangle and two smaller polygons, and take the sum of their scores
33 int score = dfs(start, k) + dfs(k, end) + vertexValues[start] * vertexValues[k] * vertexValues[end];
34 // Find the minimum score from all possible partitions
35 minScore = Math.min(minScore, score);
36 }
37
38 // Cache the calculated minimum score
39 memoization[start][end] = minScore;
40 return minScore;
41 }
42}
43
1class Solution {
2public:
3 int minScoreTriangulation(vector<int>& values) {
4 int n = values.size();
5 // Dynamic programming matrix to store the minimum scores
6 vector<vector<int>> dp(n, vector<int>(n, 0));
7
8 // A lambda function that performs a depth-first search to find the minimum score
9 function<int(int, int)> dfs = [&](int left, int right) -> int {
10 // Base case: if only two vertices, no triangle can be formed
11 if (left + 1 == right) {
12 return 0;
13 }
14 // If we have already computed this subproblem, return the stored value
15 if (dp[left][right]) {
16 return dp[left][right];
17 }
18 // Initialize the answer to a high value. (1 << 30) represents a large number.
19 int ans = 1 << 30;
20 // Consider all possible points 'k' for triangulating the polygon
21 for (int k = left + 1; k < right; ++k) {
22 // Calculate the minimum score by considering the current triangle formed by vertices left, k, right
23 // and adding the minimum scores of the two remaining sub-polygons
24 ans = min(ans, dfs(left, k) + dfs(k, right) + values[left] * values[k] * values[right]);
25 }
26 // Store the result in the dynamic programming matrix and return it
27 dp[left][right] = ans;
28 return ans;
29 };
30
31 // Call the dfs function for the entire range of the given vertices
32 return dfs(0, n - 1);
33 }
34};
35
1function minScoreTriangulation(values: number[]): number {
2 const size = values.length;
3 // Create a 2D array 'dp' for dynamic programming, initialized with zeros
4 const dp: number[][] = Array.from({ length: size }, () => Array.from({ length: size }, () => 0));
5
6 // Iterate over possible triangulations lengths
7 for (let length = 3; length <= size; ++length) {
8 // Find minimum score triangulation for each subarray of 'values' of the current length
9 for (let start = 0; start + length - 1 < size; ++start) {
10 const end = start + length - 1;
11 // Initialize a high value to find a minimum later on
12 dp[start][end] = Number.MAX_SAFE_INTEGER;
13 // Consider all points as possible third vertices to form triangles
14 for (let k = start + 1; k < end; ++k) {
15 // Update the score of the triangulation
16 dp[start][end] = Math.min(dp[start][end], dp[start][k] + dp[k][end] + values[start] * values[k] * values[end]);
17 }
18 }
19 }
20 // Return the minimum score of triangulating the whole polygon
21 return dp[0][size - 1];
22}
23
Time and Space Complexity
The provided code defines a method minScoreTriangulation
for finding the minimum score triangulation of a convex polygon with the vertices labeled by integer values. The implementation uses a top-down dynamic programming approach with memoization.
Time Complexity:
The time complexity of the algorithm can be determined by the number of unique subproblems and the time it takes to solve each subproblem. The function dfs
is called with different arguments i
and j
, which represent the indices in the values
array, effectively standing for vertices of the polygon.
Considering that i
and j
represent a range in the values
array, there are at most n
(where n
is the length of values
) choices for i
, and for every i
, there are at most n
choices for j
. This gives us n^2
unique ranges.
Inside each call to dfs
, there is a for loop that iterates up to n
times, which suggests that each subproblem is solved in O(n)
time. However, due to the memoization (@cache
), these subproblems are solved only once, and the subsequent calls retrieve the results in O(1)
time.
Hence, the overall time complexity is O(n^3)
, since we have n^2
subproblems, and each takes O(n)
time to compute initially.
Space Complexity:
The space complexity is determined by the space required for memoization and the depth of the recursion stack.
- The memoization table or cache will store the results for each unique pair of
i
andj
, resulting inO(n^2)
space. - The maximum depth of the recursion tree can be
n
in case of a linear sequence of recursive calls, therefore addingO(n)
space complexity.
Together, the space complexity of the algorithm is O(n^2)
due to memoization being the dominant term.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!