golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2022-12-06 13:43:37

func minScoreTriangulation(A []int) int {
	n := len(A)

	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
	}

	for i := n - 3; i >= 0; i-- {
		for j := i + 2; j < n; j++ {
			for k := i + 1; k < j; k++ {
				if dp[i][j] == 0 {
					dp[i][j] = dp[i][k] + A[i]*A[k]*A[j] + dp[k][j]
				} else {
					dp[i][j] = min(dp[i][k]+A[i]*A[k]*A[j]+dp[k][j], dp[i][j])
				}

			}
		}
	}
	
	return dp[0][n-1]
}

func min(x, y int) int {
	if x < y {
		return x
	}

	return y
}

javascript 解法, 执行用时: 72 ms, 内存消耗: 42.2 MB, 提交时间: 2022-12-06 13:42:39

/**
 * 这道题目的关键是:
 * 可以把任何顶点数大于3的凸多边形分解为一个三角形和至多两个凸多边形，并且按这种
 * 方式分割，最后n个顶点得到的一定是n - 2个三角形（我不知道最后得到的一定是n - 2个三角形怎么证明
 * ）。
 * 那么这个就可以dp了
 * @param {number[]} A
 * @return {number}
 */
var minScoreTriangulation = function(A) {
    const len = A.length
    const dp = new Array(len)
    // 因为dp求的是最小值，那么初始化为最大值
    for(let i = 0;i < len;i++) dp[i] = new Array(len).fill(Infinity)
    for(let i = 0;i < len;i++) {
        // 顶点数小于3不能构成三角形，dp中不会有用到顶点数为1的情况。
        //i、j包含顶点数小于2的情况的值都初始化为0,便于后面计算
        dp[i][(i + 1) % len] = 0
    }
    // temp_len + 1代表凸多边形的顶点个数
    // dp先求凸多边形有3个定点的情况，再求有4个顶点的情况下，直至求出有length个顶点的情况
    for(let temp_len = 2;temp_len < len;temp_len++) {
        // 这些顶点中第一个顶点是i，最后一个顶点是j。
        // i和j都有可能为0 ~ (len - 1)（开闭区间）中的任何一个点
        for(let i = 0;i < len;i++) {
            let j = (i + temp_len) % len
            // 虽然是循环的，但可以认为j在i的后面，也就是k永远不可能等于i或j
            for(let k = (i + 1) % len;k !== j;k = (k + 1) % len) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])
            }
        }
    }
    return dp[0][len - 1]
};

python3 解法, 执行用时: 164 ms, 内存消耗: 15.6 MB, 提交时间: 2022-12-06 13:41:39

'''
dp[i][j]：表示从第i个到第j个角所形成的三角形的最小面积

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])
'''
class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        @lru_cache(None)
        def dp(i, j):
            res = 10000009
            for k in range(i + 1, j):
                res = min(res, dp(i, k) + dp(k, j) + A[i] * A[j] * A[k])
            return res % 10000009

        return dp(0, len(A) - 1)

python3 解法, 执行用时: 156 ms, 内存消耗: 15.7 MB, 提交时间: 2022-12-06 13:40:35

from functools import lru_cache

class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        @lru_cache(None)
        def dfs(left, right):
            if left + 1 == right:
                return 0
            ans = float('inf')
            for k in range(left + 1, right):
                ans = min(ans, dfs(left, k) + dfs(k, right) + A[left] * A[k] * A[right])

            return ans

        return dfs(0, len(A) - 1)

python3 解法, 执行用时: 104 ms, 内存消耗: 15 MB, 提交时间: 2022-12-06 13:39:58

'''
dp[i][j]：表示从第i个到第j个角所形成的三角形的最小面积

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])
'''
class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        length = len(A)
        inf = float('inf')
        dp = [[inf for _ in range(length)] for _ in range(length)]

        for i in range(length - 1):
            dp[i][i + 1] = 0

        for d in range(2, length):
            for i in range(0, length - d):
                j = i + d
                for k in range(i + 1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])

        return dp[0][length - 1]