給定 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。

圖解狀態(tài)轉(zhuǎn)移

dp[i][j]代表區(qū)間（i，j）內(nèi)多邊形進(jìn)行三角剖分后可以得到的最低分

代碼

class Solution {public int minScoreTriangulation(int[] A) {int n=A.length;int[][] dp=new int[n][n];for(int i=0;i<n;i++)Arrays.fill(dp[i],Integer.MAX_VALUE);for(int i=0;i<n;i++)dp[i][(i+1)%n]=0;for(int len=2;len<n;len++)for (int left=0;left<n;left++){int right=(left+len)%n;for(int loc=(left+1)%n;loc!=right;loc=(loc+1)%n)dp[left][right]= Math.min(dp[left][right],dp[left][loc]+dp[loc][right]+A[loc]*A[left]*A[right]);}return dp[0][n-1];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode1039. 多边形三角剖分的最低得分（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。