题目链接:https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/
题目大意:给出一个凸多边形,每个顶点有一个值values[i]
,顶点按照顺时针给出。将其三角化,每个三角形的值是三个顶点值的乘积,一个三角化方法的值是所有三角形的值的和。求三角化方法最低取得的值。
思路:凸多边形三角化上一次碰到还是卡塔兰数(凸多边形三角化的方案数就是卡塔兰数)。但具体记不太清了。先想着的是一共有3n-6个数,其中n个数必然是凸多边形的顶点。剩下的2n-6个数是重复一遍的,也就是n-3个数。但怎么算最终值有点没想出来。
看了题解后,知道了可以dp来做,就是分割任务。对一条凸多边形的边i-j来说,最终的最优值就是i-j-k(三角形)+ i-k(凸多边形)+ k-j(凸多边形)。两个凸多边形可以递归。
但我把递归的dfs函数写在外面时,就超时了,只有和题解一样用lambda表达式写dfs函数才能通过。应该是lambda表达式函数调用开销小,局部性更好吧。
关于lambda表达式的递归,这篇文章很详细:https://blog.csdn.net/J__M__C/article/details/125437699
完整代码
class Solution {
public:int minScoreTriangulation(vector<int>& v) {int n = v.size();vector<vector<int>> dp(n, vector<int>(n, -1)); auto dfs = [&](auto&& self, int i, int j) -> int {if (i + 1 == j)return 0; int &res = dp[i][j];if (res != -1) return res;res = INT_MAX;for (int k = i + 1; k < j; k++) {res = min(res, self(self, i, k) + self(self, k, j) + v[i] * v[j] * v[k]);}return res;};return dfs(dfs, 0, n - 1);}
};