[C++/Python] O(n^3) DP explanation + diagrams
Explanation: \n\nIn any valid triangulation, every edge of the polygon must be a part of exactly one triangle:\n If it werent part of a triangle, the polygon wo
**Explanation**: \n\nIn any valid triangulation, every edge of the polygon must be a part of exactly one triangle:\n* If it werent part of a triangle, the polygon wouldnt be fully triangulated.\n* If it were part of more than one triangle, those triangles would have to be overlapping.\n\nConsider the edge between the first and last vertices:\n![image](https://assets.leetcode.com/users/karutz/image_1557029962.png)\n\nIn general, there are `n - 2` choices of triangle for a polygon with `n` vertices.\nWe can try every triangle and solve the resulting subproblems recursively:\n\n![image](https://assets.leetcode.com/users/karutz/image_1557030892.png)\n\nUse dynamic programming to avoid recomputation and build smaller solutions into bigger ones.\n\n**Complexity**: \n\nThere are `O(n^2)` states: one for every subarray of `A`, `A[i:j], 0 <= i < j <= n`.\nEach state takes `O(n)` work.\n\nOverall complexity: `O(n^3)`.\n\n**Top-down Python3**:\n```python\nfrom functools import lru_cache\n\nclass Solution:\n    def minScoreTriangulation(self, A):\n        @lru_cache(None)\n        def dp(i, j):\n            if j - i + 1 < 3:\n                return 0\n            return min(A[i]*A[j]*A[k] + dp(i, k) + dp(k, j) for k in range(i + 1, j))\n        return dp(0, len(A) - 1)\n```\n\n**Bottom-up C++**:\n```c++\nclass Solution {\npublic:\n    int minScoreTriangulation(vector<int>& A) {\n        int n = A.size();\n        int dp[50][50] = {};\n        for (int sz = 2; sz < n; sz++) {\n            for (int i = 0; i + sz < n; i++) {\n                int j = i + sz;\n                dp[i][j] = 1e9;\n                for (int k = i + 1; k < j; k++) {\n                    dp[i][j] = min(dp[i][j], A[i]*A[j]*A[k] + dp[i][k] + dp[k][j]);\n                }\n            }\n        }\n        return dp[0][n - 1];\n    }\n};\n```
[]