Python: From DP n^2 -> n -> O(1)
You try splitting a number into sums like 1+4, 2+3, 3+2, 4+1\nThen you try splitting right summand 4 -> 2+2, 3 -> 2+1, 2 -> 1+1, ... and so on. \nYou see repeat
You try splitting a number into sums like 1+4, 2+3, 3+2, 4+1\nThen you try splitting right [summand](https://en.wiktionary.org/wiki/summand) 4 -> 2+2, 3 -> 2+1, 2 -> 1+1, ... and so on. \nYou see repeated (overlapping) & dependent (optimal substructure) subprobles and click - DP.\nYou can draw an n-ary tree and see yourself.\n\n**DP: top-down approach + memo O(n^2)**\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        @cache\n        def dfs(a):\n            if a == 1:\n                return 1\n            \n            max_res = 1\n            for right in range(1, a):\n                left = a - right\n\t\t\t\t# you can chose left side * right side (e.g. 10: 5 x 5 = 25)\n\t\t\t\t# or you can carry on splitting 5 * f(5) => 5 * (3 * 2) = 30\n                max_res = max(max_res, left * right, left * dfs(right))\n            \n            return max_res\n        \n        return dfs(n)\n```\n\n**DP: bottom-up O(n^2)**\nThe same as above but without stack.\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        dp = [1] * (n + 1)\n\n        for i in range(2, n + 1):\n            max_res = 1\n            for right in range(2, i):\n                left = i - right\n                max_res = max(max_res, left * right, left * dp[right])\n            dp[i] = max_res\n        \n        return dp[n]\n```\n\n---\nThe logic/code above was what comes first aka bruteforce.\n\n---\n**Futher observations:**\nIf you calc max products for the first 12 elements you\'ll see the following:\n```\nnum sum     #2 #3\n 2  1+1      0  0\n 3  2+1      1  0\n ---\n 4  2+2      2  0\n 5  2+3      1  1\n 6  3+3      0  2\n ---\n 7  2+2+3    2  1\n 8  2+3+3    1  2\n 9  3+3+3    0  3\n ---\n10  2+2+3+3  2  2\n11  2+3+3+3  1  3\n12  3+3+3+3  0  4\n```\n**Observations: #1**\nYou can see that the difference between n=4,5,6 and n=7,8,9 is the [summand](https://en.wiktionary.org/wiki/summand) +3\nBetween n=7,8,9 and n=10,11,12 the summond is again +3 and so on...\n\n**DP: bottom-up O(n)**\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        dp = [0,1,1,2,4,6,9] + [0] * (max(0, n - 6))\n        \n        for i in range(7, n + 1):\n            dp[i] = 3 * dp[i - 3]\n        \n        return dp[n]\n```\n**Observations: #2**\nNow look at number of 2 and 3 summands for element n=4+?\nDo you see the pattern? No?!\nFor 2 it\'s 210 210 210 210 ...\nFor 3 it\'s 012 123 234 345 ...\n\nWe can extract it into a formula: `2 ^ (2 - (n - 1) % 3) * 3 ^ ((n - 1) % 3 + (n - 1 - 3) // 3)`\nI intentionally left it w/o simplification so that it\'s easier to understand it.\nNow you can apply the formula to n > 3 and return hardcoded values for n=2 and n=3.\n\n**Math: O(1)**\nTook me 15 minutes to extract the formula. No way I am going to extract it quickly under pressure.\n\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n == 2: return 1\n        elif n == 3: return 2\n        else:\n            # return 2 ** (2 - (n - 1) % 3) * 3 ** ((n - 1) % 3 + (n - 1 - 3) // 3) # log(n)\n            n -= 1\n            return int(math.pow(2, (2 - n % 3))) * int(math.pow(3, (n % 3 + (n - 3) // 3))) # O(1)\n```\n\nP.S. An interesting fact about python\'s power operator ** O(log(n)) vs pow(x,y) O(1) is [here](https://stackoverflow.com/questions/48839772/why-is-time-complexity-o1-for-powx-y-while-it-is-on-for-xy) \n\n**If you like it, upvote!**
['Dynamic Programming', 'Python']