# LeetCode: 343. 整数拆分¶

## 2、解题思路¶

2:  1
3:  2
4:  4
5:  6
6:  9
7:  12
8:  16
9:  24
10: 36


dp[i] = max(dp[1]*(n-1),dp[2]*(n-2),...,dp[n-1]*1,1*(n-1),2*(n-2),...,(n-1)*1)


• 前面求解的最优值与差值求和

• 在这里面，我们发现，实际上并不需要每一项都判断，

• 直接两个数相乘

• 如果是偶数，就是(n/2)*(n/2)

• 如果是奇数，就是(n/2)*(n/2+1)

class Solution:
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0, 1, 1, 2, 4, 6, 9, 12, 18]

length = len(dp)
if n < length:
return dp[n]

dp.extend([0] * (n - length + 1))

for i in range(length, n + 1):
half = i // 2
if i % 2 == 0:

dp[i] = max(dp[i], dp[half] * dp[half], half * half, dp[i - 2] * 2, dp[i - 3] * 3)
else:
dp[i] = max(dp[i], dp[half] * dp[half + 1], half * (half + 1), dp[i - 2] * 2, dp[i - 3] * 3)

return dp[n]


​ 实际上，只有2，3的情况特殊，其他的情况，都能够用中间的两个最大的值所得到

class Solution:
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0, 1, 1, 2, 4, 6, 9, 12, 18]

length = len(dp)
if n < length:
return dp[n]

dp.extend([0] * (n - length + 1))

for i in range(length, n + 1):
half = i // 2
if i % 2 == 0:

dp[i] = max(dp[half] * dp[half], dp[i - 2] * 2, dp[i - 3] * 3)
else:
dp[i] = max(dp[half] * dp[half + 1], dp[i - 2] * 2, dp[i - 3] * 3)

return dp[n]


​ 又到网上查了一下，整数拆分实际上是一个数学问题，