0343. 整数拆分 #

标签：数学、动态规划
难度：中等

题目大意 #

描述：给定一个正整数 $n$，将其拆分为 $k (k \ge 2)$ 个正整数的和，并使这些整数的乘积最大化。

要求：返回可以获得的最大乘积。

说明：

$2 \le n \le 58$。

示例：

示例 1：

1
2
3


输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2：

1
2
3


输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

解题思路 #

思路 1：动态规划 #

1. 划分阶段 #

按照正整数进行划分。

2. 定义状态 #

定义状态 $dp[i]$ 表示为：将正整数 $i$ 拆分为至少 $2$ 个正整数的和之后，这些正整数的最大乘积。

3. 状态转移方程 #

当 $i \ge 2$ 时，假设正整数 $i$ 拆分出的第 $1$ 个正整数是 $j(1 \le j < i)$，则有两种方法：

将 $i$ 拆分为 $j$ 和 $i - j$ 的和，且 $i - j$ 不再拆分为多个正整数，此时乘积为：$j \times (i - j)$。
将 $i$ 拆分为 $j$ 和 $i - j$ 的和，且 $i - j$ 继续拆分为多个正整数，此时乘积为：$j \times dp[i - j]$。

则 $dp[i]$ 取两者中的最大值。即：$dp[i] = max(j \times (i - j), j \times dp[i - j])$。

由于 $1 \le j < i$，需要遍历 $j$ 得到 $dp[i]$ 的最大值，则状态转移方程如下：

$dp[i] = max_{1 \le j < i}\lbrace max(j \times (i - j), j \times dp[i - j]) \rbrace$。

4. 初始条件 #

$0$ 和 $1$ 都不能被拆分，所以 $dp[0] = 0, dp[1] = 0$。

5. 最终结果 #

根据我们之前定义的状态，$dp[i]$ 表示为：将正整数 $i$ 拆分为至少 $2$ 个正整数的和之后，这些正整数的最大乘积。则最终结果为 $dp[n]$。

思路 1：代码 #

1
2
3
4
5
6
7


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]

思路 1：复杂度分析 #

时间复杂度：$O(n^2)$。
空间复杂度：$O(n)$。