LeetCode - 1039. Minimum Score Triangulation of Polygon

链接：https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/
难度：medium

解题思路：
学习了一下卡特兰动态规划（Catalan）大部分的教程都是用循环完成的，但感觉递归更容易理解一点。
二维数据out[i][j]用来记录，从顶点i到顶点j的结果（此处为顶点乘积之和最小值）。
我们将图割裂成三部分来看，三角形的左边，三角形顶点乘积，以及三角形的右边。如果图形为三角形，那么左右的面积均为0，结果即三角形的顶点乘积。
我们都按顶点的升序来构造三角形，那么顶点相邻或者一样的时候无法构成三角形，直接返回0。

• 假设输入为三角形，因为m-i=j-m<=1，那么
  out[0][2]=A[0]A[1]A[2]+out[0][1]+out[1][2]=A[0]A[1]A[2]+0+0
• 假设输入为四边形，那么
  out[0][3]=min(out[0][1]+out[1][3]+A[0]A[1]A[3], out[0][2]+out[2][3]+A[0]A[2]A[3])，而out[1][3]即顶点为013组成的三角形的右边的图形的计算结果；out[0][2]即顶点为023组成的三角形的左边图形的计算结果
• 假设输入为五边形，那么同理
  out[0][4]=min(out[0][1]+out[1][4]+A[0]A[1]A[4], out[0][2]+out[2][4]+A[0]A[2]A[4], out[0][3]+out[3][4]+A[0]A[3]A[4])
• 不一一列举

class Solution {
    int [][]out;
    public int minScoreTriangulation(int[] A) {
        out = new int[A.length][];
        for(int i = 0; i < A.length; i ++) {
            out[i] = new int[A.length];
        }
        
        return calc(A, 0, A.length - 1);  
    }

    private int calc(int[] A, int i, int j) {
        if(j - i <= 1) return 0;
        if(out[i][j] != 0) return out[i][j];

        int min = Integer.MAX_VALUE;
        for(int m = i + 1; m < j; m ++) {
            int sum = calc(A, i, m) + calc(A, m, j) + A[i] * A[j] * A[m];
            if(sum < min) {
                min = sum;
            }
        }
        out[i][j] = min;
        return out[i][j];

    }
    
}

执行用时： 2 ms , 在所有 Java 提交中击败了 100.00% 的用户
内存消耗： 36.4 MB , 在所有 Java 提交中击败了 42.24% 的用户