【lambda表达式】【DP】个人练习-Leetcode-1039. Minimum Score Triangulation of Polygon

题目链接：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);
    }
};