1039. Minimum Score Triangulation of Polygon

leetcode medium

#array#backtracking#csharp#dynamic-programming#leetcode#math#medium

Task

У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника.

Пример:

Input: values = [1,2,3]

Output: 6

C# solution

matched/original

public class Solution {
    public int MinScoreTriangulation(int[] values) {
        int n = values.Length;
        int[,] dp = new int[n, n];
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i, j] = int.MaxValue;
                for (int k = i + 1; k < j; ++k) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k, j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0, n - 1];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinScoreTriangulation(vector<int>& values) {
        int n = values.size();
        int[,] dp = new int[n, n];
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i, j] = int.MaxValue;
                for (int k = i + 1; k < j; ++k) {
                    dp[i, j] = min(dp[i, j], dp[i, k] + dp[k, j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0, n - 1];
    }
}

Java solution

matched/original

public class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}

JavaScript solution

matched/original

var minScoreTriangulation = function(values) {
    const n = values.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    for (let length = 2; length < n; length++) {
        for (let i = 0; i < n - length; i++) {
            const j = i + length;
            dp[i][j] = Infinity;
            for (let k = i + 1; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
            }
        }
    }
    
    return dp[0][n - 1];
};

Python solution

matched/original

def minScoreTriangulation(values):
    n = len(values)
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k])
                
    return dp[0][n - 1]

Go solution

matched/original

import "math"

func minScoreTriangulation(values []int) int {
    n := len(values)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for length := 2; length < n; length++ {
        for i := 0; i < n-length; i++ {
            j := i + length
            dp[i][j] = math.MaxInt32
            for k := i + 1; k < j; k++ {
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+values[i]*values[j]*values[k])
            }
        }
    }

    return dp[0][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализация:

Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j.

Основное заполнение dp:

Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n).

Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника.

Заполнение dp для каждого подмногоугольника:

Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j.

Возврат результата:

Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника.

😎