blob: b8d5a0f91f1f4cf448bf60971ad6e940904a721b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
# 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
|