1039. Minimum Score Triangulation of Polygon

MediumArrayDynamic Programming
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

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 is 0.

For the recursive step:

  • We loop through all possible third vertices k for the triangle, where k ranges from i+1 to j-1.
  • For each k, we calculate the score of the triangle formed by vertices i, k, and j, which is values[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) and dfs(k, j) representing the minimum score from i to k and from k to j, respectively.
  • The min function is applied to choose the smallest possible score amongst all combinations of k.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

Example 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):

  1. We need to triangulate the polygon from vertex 0 to vertex 3, hence we call dfs(0, 3).

  2. Since i + 1 does not equal j, we proceed to find the minimum triangulation score.

    • We have two possibilities for vertex k as the third vertex for the triangle since k can be either 1 or 2.

  3. For k = 1:

    • We calculate the score of the triangle [0, 1, 3] which is 1 * 3 * 4 = 12.
    • We then add this score to the score for the remaining sub-polygon formed by the vertices 0 to 1, and 1 to 3. Here, the sub-polygon 0-1 is just a line and does not form a triangle, so dfs(0, 1) is 0, and we need to calculate dfs(1, 3).
    • Now, for dfs(1, 3), we have only two points so again it does not form a triangle, resulting in score 0.
    • The total for k = 1 is 12 + 0 + 0 = 12.

  4. For k = 2:

    • We calculate the score of the triangle [0, 2, 3] which is 1 * 1 * 4 = 4.
    • We again add this score to the score for the sub-polygon formed by vertices 0 to 2, and 2 to 3. The sub-polygon 2-3 is just a line, so dfs(2, 3) is 0.
    • We need to calculate dfs(0, 2). This is a triangle [0, 1, 2] with a score 1 * 3 * 1 = 3.
    • So, the total for k = 2 is 4 + 3 + 0 = 7.

  5. We select the minimum score for our two k options, which is 7, so dfs(0, 3) returns 7.

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
Not Sure What to Study? Take the 2-min Quiz

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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 and j, resulting in O(n^2) space.
  • The maximum depth of the recursion tree can be n in case of a linear sequence of recursive calls, therefore adding O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

Dynamic Programming Introduction and Patterns

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«