题目描述：
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
我的作答：
思路就是递归，取两个数的最大值和一个数乘以另一个数拆分后的最大值的最大值；我觉得递归好难啊啊啊啊啊；
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n==0 or n==1: return 0
if n==2: return 1
dp = [0]*(n+1) #dp是每一个数能分裂得到的乘积最大值
dp[2] = 1
for i in range(3, n+1):
for j in range(1, i//2+1): #超过i//2时就是一样的（对称）
dp[i] = max(dp[i], (i-j)*j, dp[i-j]*j)
return dp[n]
参考：
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 3:
return 1 * (n - 1) # 对于n小于等于3的情况，返回1 * (n - 1)
dp = [0] * (n + 1) # 创建一个大小为n+1的数组来存储最大乘积结果
dp[1] = 1 # 当n等于1时，最大乘积为1
dp[2] = 2 # 当n等于2时，最大乘积为2
dp[3] = 3 # 当n等于3时，最大乘积为3
# 从4开始计算，直到n
for i in range(4, n + 1):
# 遍历所有可能的切割点
for j in range(1, i // 2 + 1):
# 计算切割点j和剩余部分(i - j)的乘积，并与之前的结果进行比较取较大值
dp[i] = max(dp[i], dp[i - j] * dp[j])
return dp[n] # 返回整数拆分的最大乘积结果
标签：return,乘积,示例,int,最大值,随想录,103,dp,刷题 From： https://blog.csdn.net/Aerochacha/article/details/145160416