leetcode-1039. 多边形三角剖分的最低得分

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        unordered_map<int, int> memo; // memo是用来记录子问题的解，避免重复计算
        int n = values.size();
        function<int(int, int)> dp = [&](int i, int j) -> int { // dp函数是用来计算子问题的解
            if (i + 2 > j) { // 当前的多边形边数小于3，不需要进行三角剖分，得分为0
                return 0;
            }
            if (i + 2 == j) { // 当前的多边形边数等于3，只有一种剖分方式，直接计算得分
                return values[i] * values[i + 1] * values[j];
            }
            int key = i * n + j; // 将子问题的i和j作为key，保存子问题的解
            if (!memo.count(key)) { // 如果当前子问题没有被计算过，进行计算
                int minScore = INT_MAX; // 初始化当前子问题的最小得分
                for (int k = i + 1; k < j; k++) { // 枚举剖分点k，计算最小得分
                    minScore = min(minScore, values[i] * values[k] * values[j] + dp(i, k) + dp(k, j));
                }
                memo[key] = minScore; // 将子问题的解保存到memo中
            }
            return memo[key]; // 返回子问题的解
        };
        return dp(0, n - 1); // 计算整个多边形的最小得分
    }
};

解题思路

这道题可以使用动态规划（DP）来求解。具体来说，可以定义一个 DP 函数 dp(i, j)，表示对于多边形的第 i 个顶点到第 j 个顶点之间的区间，选择不相交的对角线将其分成若干个三角形的最小得分之和。那么最终的答案即为 dp(0, n-1)，其中 n 是顶点的个数。

对于 dp(i, j)，可以枚举 i 和 j 之间的所有顶点 k，并尝试将顶点 i 和顶点 j 之间的一条对角线连接起来，将多边形分成两个部分。然后分别递归求解左右两个部分的最小得分之和，并将其加上当前三角形的得分，得到当前方案的总得分。最后取所有方案的总得分中的最小值即可。

为了避免重复计算，可以使用备忘录（memoization）技术对已经计算过的结果进行缓存。首先创建了一个 unordered_map<int, int> 类型的 memo 变量，用于记录已经计算过的子问题的答案，以避免重复计算。

然后定义了一个名为 dp 的 lambda 函数，它的输入参数为两个整数 i 和 j，输出一个整数，代表计算多边形顶点 i 到顶点 j 之间构成的三角形的最小分数。这个 lambda 函数内部采用记忆化搜索的方式来避免重复计算。首先检查是否已经计算过当前子问题的答案，如果没有则通过遍历顶点 i 到顶点 j 之间的所有可能的三角形，分别计算分数，然后取最小值并将结果存入 memo 中。

最后调用 dp 函数计算多边形从顶点 0 到顶点 n-1 之间构成的三角形的最小分数，并将结果作为函数的返回值。

综上，这段代码实现了一种动态规划算法，用于计算多边形中所有可能的三角形分割方案中的最小分数。其中使用了记忆化搜索来避免重复计算，lambda 函数 dp 中定义了具体的计算逻辑。

lamda表达式和function

这段代码是最复杂的：

1	function<int(int, int)> dp = [&](int i, int j) -> int {}

这行代码定义了一个函数对象 dp，这个函数对象是一个 std::function 类型的变量，它指向一个以 int 和 int 为输入参数，以 int 为返回值的函数。

具体来说，function<int(int, int)> 表示 dp 是一个函数对象，它接受两个 int 类型的参数，返回一个 int 类型的值。这个函数对象在后面的实现中被赋值为一个 lambda 表达式，这个 lambda 表达式定义了动态规划的状态转移方程。

& 符号表示通过引用捕获外部变量，[&] 表示以引用的方式捕获所有外部变量，即函数对象内部可以访问外部的变量和函数。在本例中，lambda 表达式需要访问 values 和 memo 这两个变量。

-> int 表示函数对象返回值的类型是 int，dp(i, j) 表示函数对象的调用方式，即传入两个参数 i 和 j 并返回一个 int 类型的值。

总之，这行代码定义了一个函数对象 dp，它表示动态规划中的状态转移方程。在实际运行中，通过调用 dp(i, j) 可以计算出以 i 和 j 为顶点的三角形的最小得分，并且使用 memo 对已经计算过的值进行了缓存，以避免重复计算。