1039. Minimum Score Triangulation of Polygon

Leetcode link

题目简介

题目给我们一个参数数组 values 代表一个凸多边形的顶点集合，数组的顺序代表了多边形沿顶点顺时针的顶点的价值

题目要求我们对多边形进行三角剖分（将其分割成多个三角形）剖分出的三角形的价值是三个顶点价值的乘积

最后我们需要求出所有三角形价值之和最小的值是多少

解题思路

这一题需要慢慢推导，我们先从三角形开始：假设一开始题目给了三个顶点 [1,2,3]

则这个三角形的价值就是三个顶点相乘，也就是 6

接下来是正方形 [3,7,4,5]：

3--7
|  |
5--4

我们可以选取相邻的两个点 [3, 5] 他们会组成一条边，基于这条边，我们可以再任意选取一点（假设是 7）

此时我们可以将正方形剖分成两个三角形：[3, 5, 7]，[5, 7, 4] 此时我们已经将问题拆分成了处理三角形的模式

接下来我们来看看正五边形：

   1
 /   \
5     2
 \   /
  4-3

我们一样可以选取相邻的两个点 [1, 5]，基于这条边我们再任意选取一个点（假设是 3）

此时我们可以将正五边形拆分成一个三角形 [1, 5, 2] 以及一个四边形 [5, 2, 3， 4]

其中三角形我们可以用一开始的方式来处理、四边形也可以继续用上面方式处理……

看到规律了吧！

接下来我们来聊聊怎么构建这个算法

这个算法的初始是由两个点组成的，我们可以使用一个二维数组 dp[i][j] 来表示点 [i, j] 组成的边进行剖分之后的价值

这两个点我们选择数组的第一个以及最后一个元素（因为这样一来我们可以通过 j-i <=1 来判断剩下的点是否可以组成三角形）

然后我们需要构建一个 helper 函数使用递归的方式慢慢剖分多边形

Javascript

/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function (values) {
    const len = values.length
    const dp = new Array(len).fill().map(item => new Array(len).fill(0))

    return helper(dp, values, 0, len - 1)
};

const helper = (dp, values, i, j) => {
    // cannot form triangles
    if (j - i <= 1) {
        return 0
    }
    if (dp[i][j] !== 0) {
        return dp[i][j]
    }

    let minRes = Number.MAX_SAFE_INTEGER
    for (let k = i + 1; k < j; k++) {
        const curRes = values[i] * values[j] * values[k] + helper(dp, values, i, k) + helper(dp, values, k, j)
        minRes = Math.min(minRes, curRes)
    }
    dp[i][j] = minRes

    return dp[i][j]
}