[Python] From backtracking to Top down DP - O(N^2) - Clean & Concise
\u274C Solution 1: Backtracking\npython\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        self.ans = 0\n        \n        def bt(n, product,
**\u274C Solution 1: Backtracking**\n```python\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        self.ans = 0\n        \n        def bt(n, product, k):\n            if n == 0:\n                if k >= 2:\n                    self.ans = max(self.ans, product)\n                return\n            \n            for i in range(1, n+1):\n                bt(n - i, product * i, k + 1)\n                   \n        bt(n, 1, 0)\n        return self.ans\n```\n\n---\n**\u2714\uFE0F Solution 2: Top down DP**\n- Let `dp(n, k)` (where n <= 58, k <= 2) denote the maximum product we can get if we split `n` into positive integers. (k == 2 means split into >= 2 positive integer).\n```python\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        @lru_cache(None)\n        def dp(n, k):\n            if n == 0:\n                if k == 2:\n                    return 1\n                return 0\n\n            ans = 0\n            for x in range(1, n + 1):\n                ans = max(ans, dp(n - x, min(k + 1, 2)) * x)\n            return ans\n\n        return dp(n, 0)\n```\nComplexity:\n- Time: `O(N^2)`, where `N <= 58`.\n- Space: `O(N)`
[]