10-06 leetcode 0343
链接 343. Integer Break
题目
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.
题解
看到最大以及拆分，第一反应就可以往 DP 上靠了
1
2
3
4
5
6
7
8
| class Solution:
def integerBreak(self, n: int) -> int:
dp = [-float('inf')] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
return int(dp[n])
|
这题还有个数学解法，我没搞懂，先列一下
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def integerBreak(self, n: int) -> int:
ret = 1
x = n
if x == 2:
return 1
if x == 3:
return 2
while x > 4:
ret *= 3
x -= 3
return ret * x
|
