1039. Minimum Score Triangulation of Polygon

LeetCode medium original: C# #array #backtracking #csharp #dynamic-programming #leetcode #math #medium

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

LeetCode Static

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

例:

Input: values = [1,2,3]

Output: 6

C# 解法

照合済み/オリジナル

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++ 解法

自動ドラフト、提出前に確認

#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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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
}

Algorithm

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

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

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

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

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

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

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

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

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

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。