[RZ] O(n ^2) DP solution and O(n) solution based on math
1. DP solution ---> O(n ^ 2)\nWe are asked to break a positive integer n into 2 or more integers with maximum product. To find the optimal breakdown, as we know
**1. DP solution ---> O(n ^ 2)**\nWe are asked to break a positive integer n into 2 or more integers with maximum product. To find the optimal breakdown, as we know each breakdown divides the original problem into sub-problems, we can try a DP approach to first calculate the results of sub-problems. \n\nAssume f[i] means the maximum product we can get to breakdown i (i <= n). \nStarting point: f[1] = 1\nTransition equation:\n```\nfor i from 2 to n:\n    for j from 1 to i / 2: ---> no need to check j > i / 2, becasue then i - j will be smaller than i / 2\n        f[i] = max(f[i], max(j, f[j]) * max(i - j, f[i - j]))\n```\nSome notes:\n1. The equation looks like a product of two numbers, how does it cover the cases that i is divided into more than 2 intergers? ---> the two factors in the multiplication can be f[j] and f[i - j], these two can further break down to a product of multiple integers\n2. Why do we have j as one of the possible factors as in max(j, f[j])? ---> As per above equation, f[j] will be the product of at least two numbers, but in some cases, j itself can be bigger than all the possible product of its breakdowns, for example, when j == 2, f[j] == 1, j is greater than f[j].\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        f = [0 for _ in range(n + 1)]\n        f[1] = 1\n        for i in range(2, n + 1):\n            for j in range(1, i // 2 + 1):\n                f[i] = max(f[i], max(j, f[j]) * max(i - j, f[i - j]))\n        return f[n]\n```\n\n**2. Math solution ---> O(n)**\nTwo important obervations:\n1. When n >= 4, by breaking it into 2 and n - 2, we get a product of 2 * (n - 2) == 2n - 4 >= 0. It means for any integer greater or equal to 4, we can further breaks it and it won\'t make the product smaller. Also we know 1 will not help to make the product bigger, so we do not want to have any integer k >= 4 or k == 1 in our final breakdown. Then the only possible k becomes 2 or 3.\n2. Since 3 + 3 == 2 + 2 + 2 == 6 and 3 * 3 > 2 * 2 * 2, as long as we have three 2s, we can change them to be two 3 to make the product bigger. So we will not have more than two 2 in the final breakdown.\n\nWith above observations, we would like to break n into as many 3 as possible until the remainder is less than or equal to 4. Why 4? Because 2 + 2 == 1 + 3 == 4 and 2 * 2 > 1 * 3, we want to break 4 into 2 * 2 instead of 3 * 1.\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n == 2:\n            return 1\n        if n == 3:\n            return 2\n        \n        res = 1\n        while n > 4:\n            res *= 3\n            n -= 3\n        return res * n\n```
['Math', 'Dynamic Programming', 'Python3']