- 标签:数学、动态规划
- 难度:中等
描述:给定一个正整数
要求:返回可以获得的最大乘积。
说明:
-
$2 \le n \le 58$ 。
示例:
- 示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
- 示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
按照正整数进行划分。
定义状态
当
- 将
$i$ 拆分为$j$ 和$i - j$ 的和,且$i - j$ 不再拆分为多个正整数,此时乘积为:$j \times (i - j)$。 - 将
$i$ 拆分为$j$ 和$i - j$ 的和,且$i - j$ 继续拆分为多个正整数,此时乘积为:$j \times dp[i - j]$。
则
由于
-
$0$ 和$1$ 都不能被拆分,所以$dp[0] = 0, dp[1] = 0$ 。
根据我们之前定义的状态,$dp[i]$ 表示为:将正整数
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
for j in range(i):
dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
return dp[n]
- 时间复杂度:$O(n^2)$。
- 空间复杂度:$O(n)$。