# 343. Integer Break """ given an integer 'n', break it into the sum of 'k' positive integers, where 'k >= 2' and maximise the product of those integers. return the maximum product you can get """ class Solution(object): def integerBreak(self, n): case = [0, 0, 1, 2, 4, 6, 9] if n < 7: return case[n] dp = case + [0] * (n - 6) for i in range(7, n + 1): dp[i] = 3 * dp[i - 3] return dp[-1] if __name__ == "__main__": obj = Solution() print(obj.integerBreak(2)) # expect: 1 print(obj.integerBreak(10)) # expect: 36