leetcode 1039. Minimum Score Triangulation of Polygon

1039. Minimum Score Triangulation of Polygon

题意：一个n多边形，如何分成n-2个三角形，使得每个三角形三个点乘积的和最小。

思路：区间dp。

dp[i][j]表示，将[i,j]的点组成的多边形的最小和。

k是(i,j)中的点。

这个多边形可以分成三个部分，多边形[i,k],多边形[k,j],三角形(i,j,k);

假设多边形[i,k],多边形[k,j]已知，遍历这个k，可以到这最小值。

然后可以将问题转化为子问题，求解多边形[i,k],多边形[k,j]的最小值。

有个小坑，这里要记忆化搜索，不然要超时。

class Solution {
public:int minScoreTriangulation(vector<int>& A) {int n = A.size();vector<vector<int>> dp(n, vector<int>(n, -1));return dfs(0, n-1, A,dp);}int dfs(int l, int r, vector<int>& A, vector<vector<int>>& dp){int result = INT_MAX;if (r - l <= 1)return dp[l][r]=0;if (dp[l][r] != -1) return dp[l][r];for (int k = l + 1; k < r; k++)result = min(result, dfs(l, k, A,dp) + dfs(k, r, A,dp) + A[l] * A[k] * A[r]);return dp[l][r]=result;}};

三层for的不好理解，只能看懂别人写的代码。