Py3 C++ dp動態規劃解Leetcode 1039 Minimum Score Triangulation of Polygon

Py3 C++ dp動態規劃解Leetcode 1039  Minimum Score Triangulation of Polygon

Py3 C++ dp動態規劃解Leetcode 1039  Minimum Score Triangulation of Polygon

凸多邊形三角化的問題，題目看起來很幾何，解法用動態規劃，多邊形的切割其實也是divide and conquer.

 [py3解請進]

-----

The problem of triangulating a convex polygon seems very geometric, but the solution is dynamic programming. The polygon cutting is actually a divide and conquer problem.

[codes on Leetcode]https://leetcode.com/problems/minimum-score-triangulation-of-polygon/solutions/7232385/divide-conquer-dp-recursion-iteration-beats-100/

[DP play list]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

# dp[i][j]=min weight for convex v[i..j]
class Solution:
    def minScoreTriangulation(self, v: List[int]) -> int:
        n=len(v)
        if n==3: return v[0]*v[1]*v[2]
        dp=[[0]*n for _ in range(n-1)]

        for d in range(2, n):
            for i in range(n-d):
                j=i+d
                w, e=1<<32, v[i]*v[j]
                for k in range(i+1, j):
                    w=min(w, e*v[k]+dp[i][k]+dp[k][j])
                dp[i][j]=w
        return dp[0][-1]