[Java] DP
dp[i][j] = min cost for A[i..j]\nbase case: if j - i + 1 == 3 (length == 3), dp[i][j] = A[i]A[i+1]A[i+2]\ndp[i][j] = dp[i][k] + dp[k][j] + A[i]A[j]A[k]\n\nin bo
dp[i][j] = min cost for A[i..j]\nbase case: if j - i + 1 == 3 (length == 3), dp[i][j] = A[i]*A[i+1]*A[i+2]\ndp[i][j] = dp[i][k] + dp[k][j] + A[i]*A[j]*A[k]\n\nin bottom up approach\none key point is we should constructure the answer start from base case\nyou can draw a graph, start from side = 4, when you separate the graph into 2 triangle, you have to know the side = 3 answer beforehand\nsame from side = 5, when you separate the graph into 1 triangle and one side = 4 shape, you have to know the side = 4 answers beforehand\nso we start from side = 3 to side = n, to construct the answer\n\n```\n    public int minScoreTriangulation(int[] A) {\n        int n = A.length;\n        int[][] dp = new int[n][n];\n        for (int side = 3; side <= n; side++) {\n            for (int i = 0, j = side-1; j < n; i++, j++) {\n                if (j - i + 1 == 3) {\n                    dp[i][j] = A[i] * A[i+1] * A[i+2];\n                } else {\n                    int min = Integer.MAX_VALUE;\n                    for (int k = i+1; k < j; k++)\n                        min = Math.min(min, dp[i][k] + dp[k][j] + A[i] * A[j] * A[k]);\n                    dp[i][j] = min;\n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n```
[]