難度：★★★★☆
類型：幾何，數(shù)組
方法：動(dòng)態(tài)規(guī)劃

題目

力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄

給定 N，想象一個(gè)凸 N 邊多邊形，其頂點(diǎn)按順時(shí)針順序依次標(biāo)記為 A[0], A[i], ..., A[N-1]。

假設(shè)您將多邊形剖分為 N-2 個(gè)三角形。對(duì)于每個(gè)三角形，該三角形的值是頂點(diǎn)標(biāo)記的乘積，三角剖分的分?jǐn)?shù)是進(jìn)行三角剖分后所有 N-2 個(gè)三角形的值之和。

返回多邊形進(jìn)行三角剖分后可以得到的最低分。

示例 1：

輸入：[1,2,3]
輸出：6
解釋：多邊形已經(jīng)三角化，唯一三角形的分?jǐn)?shù)為 6。

示例 2：

輸入：[3,7,4,5]
輸出：144
解釋：有兩種三角剖分，可能得分分別為：375 + 457 = 245，或 345 + 347 = 144。最低分?jǐn)?shù)為 144。

示例 3：

輸入：[1,3,1,4,1,5]
輸出：13
解釋：最低分?jǐn)?shù)三角剖分的得分情況為 113 + 114 + 115 + 111 = 13。

提示：

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

解答

我們先來理解一下什么是三角剖分。首先，多邊形每個(gè)頂點(diǎn)都是一個(gè)數(shù)字，三個(gè)頂點(diǎn)組成一個(gè)三角形，這個(gè)三角形的分?jǐn)?shù)就是三個(gè)頂點(diǎn)的乘積，多邊形有很多個(gè)頂點(diǎn)，需要把這些頂點(diǎn)連線，這些線不能交叉，而且所有頂點(diǎn)都需要作為至少一個(gè)連線的端點(diǎn)。這樣多邊形就變成了只由三角形組成的一個(gè)狀態(tài)。多邊形的三角剖分就是拆好的三角形的分?jǐn)?shù)之和。

我們用動(dòng)態(tài)規(guī)劃解決。

【數(shù)組定義】

多邊形各個(gè)頂點(diǎn)是按順序編了號(hào)的，一個(gè)n邊形各個(gè)頂點(diǎn)是0,1,2，...，n-1。我們從中選兩個(gè)頂點(diǎn)i和j，且j>i+1，這樣從編號(hào)i到j(luò)的所有點(diǎn)就可以組成新的多邊形了（包括三角形）。

定義數(shù)組dp，維度為n×n，dp[i][j]表示由i，i+1,i+2,...j-1,j這些點(diǎn)組成的多邊形的三角剖分最小值。

【初始狀態(tài)】

因?yàn)樽詈笠笞钚≈?，我們就把dp數(shù)組中每個(gè)點(diǎn)填充為正無窮。

【遞推公式】

這里要解決dp[i][j]怎么求的問題。對(duì)于從i到j(luò)的所有點(diǎn)（不包括i和j），任選一點(diǎn)k（i<k<j），我們實(shí)際上就把從點(diǎn)i到點(diǎn)j的多邊形劃分成了三個(gè)小塊，分別是從i到k的小多邊形，從k到j(luò)的小多邊形以及三角形ikj。這時(shí)，整體的分?jǐn)?shù)就很好計(jì)算了：

dp[k][j]+dp[i][k]+A[i]A[j]A[k]

根據(jù)題意，我們需要研究從i與j之間所有點(diǎn)k的情況，取其中最小的剖分?jǐn)?shù)，作為dp[i][j]的值。

【返回值】

根據(jù)dp數(shù)組的含義，我們需要在遍歷完成后返回dp[0][-1]即可。

【注意事項(xiàng)】

遍歷順序需要留意，因?yàn)槲覀冊(cè)谶f推公式中提到，dp[k][j]和dp[i][k]是要先于dp[i][j]計(jì)算出來的，所以j正向遍歷時(shí)，為了避免找不到緩存結(jié)果dp[k][j]和dp[i][k]的尷尬情況，我們需要將i逆序遍歷。保證遍歷過程以及dp數(shù)組更新的連續(xù)性。

最后得到dp數(shù)組實(shí)際上只有右上角半個(gè)三角形。

from typing import List


class Solution:
    def minScoreTriangulation(self, A: List[int]) -> int:
        n = len(A)
        dp = [[float('inf')] * n for _ in range(n)]
        for j in range(n):
            for i in reversed(range(j)):
                if j - i < 2:
                    dp[i][j] = 0
                else:
                    for k in range(i+1, j):
                        dp[i][j] = min(dp[i][j], A[i]*A[j]*A[k]+dp[i][k]+dp[k][j])
        return dp[0][n-1]

如有疑問或建議，歡迎評(píng)論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析