跳至主要內容

0343. 整数拆分

ITCharge大约 2 分钟

0343. 整数拆分open in new window

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

题目链接

题目大意

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

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

说明

  • 2n582 \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

解题思路

思路 1:动态规划

1. 划分阶段

按照正整数进行划分。

2. 定义状态

定义状态 dp[i]dp[i] 表示为:将正整数 ii 拆分为至少 22 个正整数的和之后,这些正整数的最大乘积。

3. 状态转移方程

i2i \ge 2 时,假设正整数 ii 拆分出的第 11 个正整数是 j(1j<i)j(1 \le j < i),则有两种方法:

  1. ii 拆分为 jjiji - j 的和,且 iji - j 不再拆分为多个正整数,此时乘积为:j×(ij)j \times (i - j)
  2. ii 拆分为 jjiji - j 的和,且 iji - j 继续拆分为多个正整数,此时乘积为:j×dp[ij]j \times dp[i - j]

dp[i]dp[i] 取两者中的最大值。即:dp[i]=max(j×(ij),j×dp[ij])dp[i] = max(j \times (i - j), j \times dp[i - j])

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

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

4. 初始条件
  • 0011 都不能被拆分,所以 dp[0]=0,dp[1]=0dp[0] = 0, dp[1] = 0
5. 最终结果

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

思路 1:代码

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(n2)O(n^2)
  • 空间复杂度O(n)O(n)