Codiwan.com

The blog for Design Patterns, Linux, HA and Myself!

This article presents the solution to the problem 1039. Minimum Score Triangulation of Polygon- Leetcode. I’ll break the solution in three connected parts:

1. Brute force solution - presents the brute force solution
2. Addition of memoization and caching to make the program faster and then
3. Implementing the dynamic programming top down approach to solve it efficiently
```		```

Given N, consider a convex N-sided polygon with vertices labelled A, A[i], ..., A[N-1]
in clockwise order.

Suppose you triangulate the polygon into N-2 triangles.  For each triangle, the value of
that triangle is the product of the labels of the vertices, and the total score of the
triangulation is the sum of these values over all N-2 triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of
the polygon.

Example 1:

Input: [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

Input: [3,7,4,5]
Output: 144
Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.
The minimum score is 144.

Example 3:

Input: [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Note:

3 <= A.length <= 50
1 <= A[i] <= 100

```
```

Let’s use this input array as our base example:

``````input := []int{
1, 2, 3, 4, 5, 6
}
``````

The length of the input array is 6 and that makes it a Hexagon, and it can be broken down into 4(6 - 2) triangles. If we remove one of those points by creating a triangle using its neighbours, we’ll get a Pentagon and a triangle and similarly we’ll get a quadrilateral and one more triangle if we remove one point from the Pentagon. This image shows the divisions by reduction of polygons point wise.

This way four triangles can be created. To find the triangles having the minimum product we’ll have to select one point at a time and reduce the polygon. So, in the brute force approach, we’ll reduce the polygon in this way:

In this image, you can see that removal of a point creates a new Pentagon and this leads to the creation of 6 pentagons. The pentagons can then be reduced to quadrilaterals like this:

So, here’s the brute force approach that I’ve come up with:

1. Pick a point at index i
2. Increment the sum by adding the product of i - 1, i, i + 1 because these three indexes will make the triangle now.
3. If there are only three elements in the array return the sum
4. If there are more than 3 elements then remove the element i from the array and go to step 1
5. Decrement the sum added in step two and increment i

There is recursion in step 4, and the elements of the array will change based on the point we pick. As the removal of the elements from array will require N operations, I’ve created a circular doubly linked list. I can remove or add the element into circular doubly linked list whenever needed.

Here’s the Brute force program for this problem:

``````type Node struct {
Val    int
Index  int
Length int
Next   *Node
Prev   *Node
}

var minSum int

func minScoreTriangulation(A []int) int {
start := &Node{
Val:   A,
Index: 0,
}
temp := start
for i := 1; i < len(A); i++ {
temp.Next = &Node{
Val:   A[i],
Prev:  temp,
Index: i,
}
temp = temp.Next
}
temp.Next = start
start.Prev = temp
minSum = math.MaxInt32
minScoreTriangulationBruteForce(start, 0, len(A))
return minSum
}

func minScoreTriangulationBruteForce(start *Node, sum, length int) {
if length == 3 {
sum += start.Val * start.Next.Val * start.Next.Next.Val
if minSum > sum {
minSum = sum
}
return
}
temp := start
for temp != nil {
remove := temp
sum += remove.Val * remove.Next.Val * remove.Prev.Val
remove.Prev.Next = remove.Next
remove.Next.Prev = remove.Prev
minScoreTriangulationBruteForce(remove.Next, sum, length-1)
remove.Prev.Next = remove
remove.Next.Prev = remove
sum -= remove.Val * remove.Next.Val * remove.Prev.Val
if temp.Next == start {
break
}
temp = temp.Next
}
return
}
``````

The `struct` `Node` represents an element from the linked list. The function `minScoreTriangulation` creates the linked list from the array and passes it to the `minScoreTriangulationBruteForce` function along with the length of the list. `minScoreTriangulationBruteForce` function then loops over each one of the element, removes them and recursively calls itself. Once the recursion is complete, it adds the element back at the same location moves to the next element.

This brute force solution has a time complexity of O(nn - 3) and that is pretty terrible.

As we are converting the polygons with n points to a new polygon with n - 1 points. There will be a number of scenarios in which polygons will be repeated. For example, if the pentagon is 1 → 2 → 3 → 4 → 5 then it’ll be reduced to quadrilaterals 1 → 2 → 3 → 4 and 2 → 3 → 4 → 5. Both these quadrilaterals have triangle 2 → 3 → 4 common which means we can cache the result of previous calculations to use them later.

To create the cache I’ll first create a hash from the elements by setting the bits in an unsigned `int64` variable. Here’s the code for creating the hash:

``````func createHash(start *Node) uint64 {
var hash uint64
temp := start
for temp != nil {
hash |= 1 << temp.Index
if temp.Next == start {
break
}
temp = temp.Next
}
return hash
}
``````

The variable `hash` has the bit set at only those indexes for which there’s an element at the same index in the array. If the elements are removed then the hash is also updated by this function:

``````func updateHash(currentHash uint64, indexToBeRemoved int) uint64 {
return currentHash ^ (1 << indexToBeRemoved)
}
``````

The index, at which the element removed, is unset from the hash.

Here’s the updated program:

``````var cache map[uint64]int
var minSum int

func minScoreTriangulation(A []int) int {
start := &Node{
Val:   A,
Index: 0,
}
temp := start
for i := 1; i < len(A); i++ {
temp.Next = &Node{
Val:   A[i],
Prev:  temp,
Index: i,
}
temp = temp.Next
}
temp.Next = start
start.Prev = temp
minSum = math.MaxInt32
cache = make(map[uint64]int)
hash := createHash(start)
minScoreTriangulationLLC(start, 0, len(A), hash)
return minSum
}

func minScoreTriangulationLLC(start *Node, sum, length int, hash uint64) int {
if cacheSum, ok := cache[hash]; ok {
sum += cacheSum
if minSum > sum {
minSum = sum
}
return sum
}
if length == 3 {
sum += start.Val * start.Next.Val * start.Next.Next.Val
if minSum > sum {
minSum = sum
}
return sum
}
currentSum := math.MaxInt32
temp := start
for temp != nil {
remove := temp
sum += remove.Val * remove.Next.Val * remove.Prev.Val
remove.Prev.Next = remove.Next
remove.Next.Prev = remove.Prev
newHash := updateHash(hash, remove.Index)
tempSum := minScoreTriangulationLLC(remove.Next, sum, length-1, newHash)
if tempSum-sum+(remove.Val*remove.Next.Val*remove.Prev.Val) < currentSum {
currentSum = tempSum - sum + (remove.Val * remove.Next.Val * remove.Prev.Val)
}
remove.Prev.Next = remove
remove.Next.Prev = remove
sum -= remove.Val * remove.Next.Val * remove.Prev.Val
if temp.Next == start {
break
}
temp = temp.Next
}
cache[hash] = currentSum
return currentSum + sum
}
``````

This program contains the code for hashing and caching along with the previous brute force program. The cache will contain the sum for all the different polygons that will be created.

Here we’ve reduced the time complexity to O(2n) but still it can be further improved. One problem that you’ll find here is high cache cardinality. Since we’re removing one point at a time, there can be multiple combinations that are possible. For example, between 2 and 5, there can be 2,3,5 or 2,3,4,5 or 2,4,5. So, to cache the result, we had to create the hash of the entire elements that were part of the polygon. Let’s quickly move on to a better solution that will be very similar to this solution only, but we’ll break the problem into 2 sub problems instead of 1 that we’ve doing earlier. This will help in efficient caching.

`````` ``````

In this image you can see that I’ve started from the first and the last element, 1 and 6, and then I’m creating a triangle using the points between 1 and 6. Then each triangle creation job is creating two polygons on the either sides of the triangle. These two new polygons will become the new subproblems that we’ll solve recursively. Here’s the program for that:

``````var cache [][]int

func minScoreTriangulation(A []int) int {
cache = make([][]int, len(A))
for i := range cache {
cache[i] = make([]int, len(A))
}
minScoreTriangulationR(A, 0, len(A)-1)
return cache[len(A)-1]
}

func minScoreTriangulationR(A []int, start, end int) int {
if math.Abs(float64(start-end)) == 1 {
return 0
}
if cache[start][end] > 0 {
return cache[start][end]
}
sum := math.MaxInt32
for i := start + 1; i < end; i++ {
tempSum := minScoreTriangulationR(A, start, i) +
minScoreTriangulationR(A, i, end) +
(A[start] * A[end] * A[i])
if tempSum < sum {
sum = tempSum
}
}
cache[start][end] = sum
return sum
}
``````

This program looks simplest of all the three programs we’ve seen today. Here, I’ve made triangles for all the elements between `start` and `end` and then calculated the sum. The minimum sum is stored in the 2D `cache` array. The 2D cache array helps in limiting the number of recursion. Since we’re using the start and the end indexes for the cache, it becomes easy to look up into it unlike the previous solution.

Here’s the GitHub link for all the programs:

Loading Comments... 