给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
解法一：暴力递归
f( k ) = a * ( k - a )
可能性分析：
假设 f ( k ) 表示 n = k 时，获得的最大乘积
a = 1 尝试 ( k - a ) 是否再拆分
- 如果不查分：res1 = a * ( k - a )
- 如果查分：res2= i * f ( k - a )
- res = max(res1, res2)
在尝试 0 到 n 所有可能性后，去最大值。
def integer_break2(n):
if n <= 2: return 1
res = 0
for i in range(1, n):
res = max(res, max(i * (n - i), i * integer_break2(n - i)))
return res
def integer_break3(n):
if n <= 2: return 1
return max(max(i * (n - i), i * integer_break3(n - i)) for i in range(1, n))
解法二：动态规划
动态规划的模式：从左向右尝试
思路
状态转移方程：$dp[i]=max(dp[i],max(j(i-j),jdp[i-j]))$
- dp[i]：n = i 时，最大乘积。
代码
def integer_break(n):
dp = [0] * (n + 1)
for i in range(2, n + 1):
max_value = 0
for j in range(1, i):
max_value = max(max_value, max(j * (i - j), j * dp[i - j]))
dp[i] = max_value
return dp[-1]
print(integer_break(10))
print(integer_break(11))