One More Graphical Explanation
Firstly, we know the answer is\n\nanswer = min(combination 1, combination 2, ..., combination n)\n\nthe first step is calculate the first combination (triangle 
Firstly, we know the answer is\n\n**answer = min(combination 1, combination 2, ..., combination n)**\n\nthe first step is calculate the first combination (triangle combinations/triangulation)\n\n**If we pick an edge, ANY edge, this edge MUST be used by all the possible combinations/triangulations, because all combinations must use this edge to form a triangle.**\n\n**pick edge (0, 1)**\n\n![image](https://assets.leetcode.com/users/images/35f349e1-d7d2-468b-bd00-4d027ba6d922_1604013225.007506.png)\n\nAs shown above, we list all possible triangles formed with `edge (0, 1)` and these triangles must belong to different combinations/triangulations (because they overlap each other), and because all combinations must use `edge (0, 1)`, the number of triangles formed with `edge (0, 1)` must be the number of possible combinations/triangulations.\n\nso we can say:\n\ncombination 1 = a triangulation that must use triangle (0, 1, 2) where `(0, 1)` is the picked edge, `2` is one of the other vertices\ncombination 2 = a triangulation that must use triangle (0, 1, 3)\ncombination 3 = a triangulation that must use triangle (0, 1, 4)\n...\ncombination n = a triangulation that must use triangle (0, 1, n)\n\nso the formula becomes\n\n**answer = min( must_use_picked_edge_with_vertex_2, use_picked_edge_with_vertex_3, ... use_picked_edge_with_vertex_n )**\n\n**find the sub problem, calculate combination 1**\n\n**Combination 1 = Use the picked edge with a picked vertex**\n\nwe picked `edge (0, 1)` and we picked `vertex 2` to calculate the score, we need\n\n**triangle (0, 1, 2) score + (min (combination 1, combination 2, ..., combination n) of shape(0, 2, 3, 4, 5))**\n\n![image](https://assets.leetcode.com/users/images/8a54a08b-e851-450b-8add-6e91bfd6dc64_1604014673.7222793.png)\n\n**Min score of (0, 2, 3, 4, 5) is now a sub problem**\n\n**same trick, we pick an edge, ANY edge, then pick a vertex to make a triangle, we calcualte: triangle + min(rest of the shape)** in this case: triangle (0,2,5) + shape(2,3,4,5)\n\n![image](https://assets.leetcode.com/users/images/bf903638-320a-4d21-8f96-b0b1cd44ccba_1604015162.7413847.png)\n\n**calculate combination 2**\n\nWe have done combination/triangulation 1, we still need to calculate 2, 3 ... n and use the **min**\n\n**use the same edge (0,1), pick the next vertex, this time we have more shapes, we need**\n\n**min(shape left) + triangle + min(shape right)**\n\n![image](https://assets.leetcode.com/users/images/48bc6739-2331-43d3-8f16-03740f268541_1604015347.0816524.png)\n\n**min (shape left) and min (shape right) are both sub problems, we have done one sub problem in combination 1, we can use the same trick to calculate both left and right**\n\nBased on this logic, coding the answer should be relatively easy now\n\n```javascript\nfunction rc (vertices, edge = [0, 1], lastVertex = vertices.length - 1, memo = {}) {\n    const memoKey = `${edge.join(\',\')},${lastVertex}`;\n    if (memo[memoKey] !== undefined) return memo[memoKey];\n\n    const [edgeStartVertex, edgeEndVertex] = edge;\n\n    let min = Infinity;\n\n    for (let i = edgeEndVertex + 1; i <= lastVertex; i++) {\n        const mustUseTriangleScore = vertices[edgeStartVertex] * vertices[edgeEndVertex] * vertices[i];\n        const leftSideMinScore = i > edgeEndVertex + 1 ? rc(vertices, [edgeEndVertex, edgeEndVertex + 1], i, memo) : 0;\n        const rightSideMinScore = i < lastVertex ? rc(vertices, [edgeStartVertex, i], lastVertex, memo) : 0;\n        min = Math.min(min, leftSideMinScore + mustUseTriangleScore + rightSideMinScore);\n    }\n\n    return memo[memoKey] = min;\n}\n\nfunction rc2 (vertices, startVertex = 0, endVertex = vertices.length - 1, memo = {}) {\n    if (endVertex - startVertex < 2) return 0;\n    \n    const memoKey = `${startVertex},${endVertex}`;\n    if (memo[memoKey] !== undefined) return memo[memoKey];\n    \n    let min = Infinity;\n    \n    for (let i = startVertex + 1; i < endVertex; i++) {\n        const mustUseTriangleScore = vertices[startVertex] * vertices[endVertex] * vertices[i];\n        const leftSideMinScore = rc2(vertices, startVertex, i, memo);\n        const rightSideMinScore = rc2(vertices, i, endVertex, memo);\n        min = Math.min(min, leftSideMinScore + mustUseTriangleScore + rightSideMinScore);\n    }\n    \n    return memo[memoKey] = min;\n}\n\nfunction dp (vertices) {\n    const dp = Array(vertices.length).fill(0).map(() => Array(vertices.length).fill(0));\n    \n    for (let start = vertices.length - 1; start >= 0; start--) {\n        for (let end = start + 2 ; end < vertices.length; end++) {\n            \n            let min = Infinity;\n            for (let vertex = start + 1; vertex < end; vertex++) {\n                const mustUseTriangleScore = vertices[start] * vertices[end] * vertices[vertex];\n                const leftSideMinScore = dp[start][vertex];\n                const rightSideMinScore = dp[vertex][end];\n                min = Math.min(min, leftSideMinScore + mustUseTriangleScore + rightSideMinScore);\n            }\n            dp[start][end] = min;\n        }\n    }\n    \n    return dp[0][vertices.length - 1];\n}\n```\n
[]