题目
Given an integer n
, break it into the sum of k
positive integers, where k >= 2
, and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Constraints:
2 <= n <= 58
思路
这道题涉及到一个数学问题,一个整数n在拆分为多个e时,所求得的乘积是最大的,不过由于e不是整数,而接近e的有2和3,所有这个问题就变成拆分多少个2和3的问题。
代码
python版本:
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0]*(n+1)
dp[:7] = [0, 0, 1, 2, 4, 6, 9]
for i in range(7, len(dp)):
dp[i] = dp[i-3]*3
return dp[n]