[python] top down dp with comments
\n"""\n\n1039. Minimum Score Triangulation of Polygon\n\nVery similiar to other problems on DP on intervals (aka MCM). You don\'t particularily need\nthe geomet
```\n"""\n\n1039. Minimum Score Triangulation of Polygon\n\nVery similiar to other problems on DP on intervals (aka MCM). You don\'t particularily need\nthe geometric intuition for this one. \n\nI copy/pasted my soln for Burst Balloons and changed the following things:\nhttps://leetcode.com/problems/burst-balloons/discuss/1755801/python-2-ways-bottom-up-and-top-down-with-comments\n\n\n1. we want to find the minimum insted of maximum so:\nret = 0\nto ret = float(\'inf\')\n\nret = max(ret, prod + dfs(left, last) + dfs(last, right))\nto ret = min(ret, prod + dfs(left, last) + dfs(last, right))\n\n2. change the base case since we need a minimum sized triangle:\n\nif left >= right:\n    return 0\n    \nto if right - left + 1 < 3:\n    return 0\n\n3. no virtual window to account for boundaries. \n\nthe "balloon" we pop is the vertex value we pick, forming the triangle of the other polygonal edges.\n\nComplexity:\n\nIt is O(n^3) for time and O(n^2) for space.\n\n\n\n\n"""\n\n  \nimport inspect\n\ndef stack_depth():\n    return len(inspect.getouterframes(inspect.currentframe())) - 1\n    \n    \nclass SolutionDFS:\n    def minScoreTriangulation(self, nums: List[int]) -> int:        \n        @cache\n        def dfs(left, right):\n            #print("{indent}dfs({left},{right}) called".format(\n            #     indent="  " * stack_depth(), left=left,right=right))\n            \n            if right - left + 1 < 3: # equivalent to left + 1 = right \n                return 0\n            \n            ret = float(\'inf\')\n            \n            for last in range(left + 1, right):\n                # remainder: we want to burst all the way to the left/right\n                prod = nums[left] * nums[last] * nums[right]\n                # note, here last is always skipped in the recursive calls below \n                ret = min(ret, prod + dfs(left, last) + dfs(last, right))\n            \n            return ret\n         \n        return dfs(0, len(nums) - 1)\n    \nSolution = SolutionDFS\n```
['Dynamic Programming', 'Python']