C++ with picture
Intuition\nIf we pick a side of our polygon, it can form n - 2 triangles. Each such triangle breaks our polygon into 2 sub-polygons. We can analyze n - 2 triang
# Intuition\nIf we pick a side of our polygon, it can form ```n - 2``` triangles. Each such triangle breaks our polygon into 2 sub-polygons. We can analyze ```n - 2``` triangles, and get the minimum score for sub-polygons using the recursion.\n![image](https://assets.leetcode.com/users/votrubac/image_1557470819.png)\nThis is how this procedure looks for a sub-polygon (filled with diagonal pattern above).\n\n![image](https://assets.leetcode.com/users/votrubac/image_1557471328.png)\n# Top-Down Solution\n\u2022\tFix one side of the polygon i, j and move k within (i, j).\n\u2022\tCalculate score of the i, k, j "orange" triangle.\n\u2022\tAdd the score of the "green" polygon i, k using recursion.\n\u2022\tAdd the score of the "blue" polygon k, j using recursion.\n\u2022\tUse memoisation to remember minimum scores for each sub-polygons.\n```\nint dp[50][50] = {};\nint minScoreTriangulation(vector<int>& A, int i = 0, int j = 0, int res = 0) {\n  if (j == 0) j = A.size() - 1;\n  if (dp[i][j] != 0) return dp[i][j];\n  for (auto k = i + 1; k < j; ++k) {\n    res = min(res == 0 ? INT_MAX : res, \n      minScoreTriangulation(A, i, k) + A[i] * A[k] * A[j] + minScoreTriangulation(A, k, j));\n  }\n  return dp[i][j] = res;\n}\n```\n# Bottom-Up Solution\nAt this point, it should not be hard to come up with a bottom-up solution. The only trick here is to move ```i``` backward. This ensures "green" and "blue" sub-polygons are processed before calculating min value for the entire polygon. It happens this way naturally with the recursive solution.\n```\nint minScoreTriangulation(vector<int>& A) {\n  int dp[50][50] = {};\n  for (int i = A.size() - 1; i >= 0; --i)\n    for (int j = i + 1; j  < A.size();  ++j)\n      for (auto k = i + 1; k < j; ++k)\n        dp[i][j] = min(dp[i][j] == 0 ? INT_MAX : dp[i][j], dp[i][k] + A[i] * A[k] * A[j] + dp[k][j]);\n  return dp[0][A.size() - 1];\n} \n```\n# Complexity Analysis\nRuntime: O(n ^ 3). This can be easily seen from the bottom-up solution.\nMemory: O(n ^ 2). We use a square matrix to store DP results.
[]