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

解題思路：
學(xué)習(xí)了一下卡特蘭動態(tài)規(guī)劃（Catalan）大部分的教程都是用循環(huán)完成的，但感覺遞歸更容易理解一點(diǎn)。
二維數(shù)據(jù)out[i][j]用來記錄，從頂點(diǎn)i到頂點(diǎn)j的結(jié)果（此處為頂點(diǎn)乘積之和最小值）。
我們將圖割裂成三部分來看，三角形的左邊，三角形頂點(diǎn)乘積，以及三角形的右邊。如果圖形為三角形，那么左右的面積均為0，結(jié)果即三角形的頂點(diǎn)乘積。
我們都按頂點(diǎn)的升序來構(gòu)造三角形，那么頂點(diǎn)相鄰或者一樣的時候無法構(gòu)成三角形，直接返回0。

• 假設(shè)輸入為三角形，因為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
• 假設(shè)輸入為四邊形，那么
  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]即頂點(diǎn)為013組成的三角形的右邊的圖形的計算結(jié)果；out[0][2]即頂點(diǎn)為023組成的三角形的左邊圖形的計算結(jié)果
• 假設(shè)輸入為五邊形，那么同理
  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];

    }
    
}

執(zhí)行用時： 2 ms , 在所有 Java 提交中擊敗了 100.00% 的用戶
內(nèi)存消耗： 36.4 MB , 在所有 Java 提交中擊敗了 42.24% 的用戶