动态规划：凸多边形最优三角剖分

大家好，我是连人，本期接着说动态规划的问题。

这是一个凸多边形。对于这个凸多边形，我们可以将弦连接，将其分为多个三角形。

那么问题来了，怎么做才能使这些三角形的权值之和最小呢？

在这里，权值可以是任何和弦长，边长有关的权函数，一般来说，我们使用三角形的边长作为权值。

在这个问题中，是具有最优子结构的。

设一共有n边的凸多边形点的集合为{v₀，v₁，… ，v_n-1}，在以v₀和v_n-1为底的情况下，求k∈（0，n-1），使v₀，v_n-1，v_k组成的三角形权值最小。

这样，剩下的两个点集{v₀，…，v_k}和{v_k，…，v_n-1}就可以组成新的凸多边形。

在其中，定义一个二维数组t[ i ][ j ]，它的含义是在凸多边形{v_i-1，v_i，…，v_j}的最优三角剖分的权值（以v_i-1，v_j为底，寻找k∈[i，j]的第三个顶点，使权值最小。这样说可能更容易理解），以i来代替i-1可以避开两个点被判定为三角形的情况所造成的麻烦。因此可得递归式：

这个式子跟矩阵连乘问题还是非常相似的，因此我们再定义一个二维数组s，负责记录在凸多边形{v_i-1，v_i，…，v_j}中的第三顶点k。

同样地，t和s只使用右上部分，对角线为0，剩下的以如下顺序记录：

这个图有点问题，因为第0行是不使用的，因为不可能有第-1个点给0当底。

作为例子的多边形是我在网上档的，因为看见好几篇都用的这个例子也无法找到原出处了。

weight = [
    [0, 2, 2, 3, 1, 4],
    [2, 0, 1, 5, 2, 3],
    [2,