Medium

题目描述

给定一个正整数 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

提示:

  • 存在一个简单的 O(n) 解法。
  • 你可以检查 n 从 7 到 10 的拆分结果来发现规律。

解题思路

这道题有两种主要解法：动态规划和数学方法。

方法一：动态规划 定义 dp[i] 表示正整数 i 拆分后能得到的最大乘积。对于每个数字 i，我们尝试将其拆分为 j 和 i-j 两部分，其中 1 ≤ j < i。对于每一种拆分，乘积为 j × max(i-j, dp[i-j])。这里用 max(i-j, dp[i-j]) 是因为 i-j 可以选择不继续拆分。

方法二：数学方法（推荐） 通过数学分析可以发现规律：要使乘积最大，应该尽可能多地拆分出数字 3。当剩余部分是 4 时，拆分为 2×2 比 3×1 更优。具体规律：

  • 当 n % 3 == 0 时，全部拆分为 3
  • 当 n % 3 == 1 时，拆分为若干个 3 和一个 4（即 2×2）
  • 当 n % 3 == 2 时，拆分为若干个 3 和一个 2

需要特别处理 n = 2 和 n = 3 的情况，因为它们必须拆分但拆分后乘积反而变小。

代码实现

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        if (n % 3 == 0) {
            return pow(3, n / 3);
        } else if (n % 3 == 1) {
            return pow(3, n / 3 - 1) * 4;
        } else {
            return pow(3, n / 3) * 2;
        }
    }
};

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        
        if n % 3 == 0:
            return 3 ** (n // 3)
        elif n % 3 == 1:
            return 3 ** (n // 3 - 1) * 4
        else:
            return 3 ** (n // 3) * 2

public class Solution {
    public int IntegerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        if (n % 3 == 0) {
            return (int)Math.Pow(3, n / 3);
        } else if (n % 3 == 1) {
            return (int)Math.Pow(3, n / 3 - 1) * 4;
        } else {
            return (int)Math.Pow(3, n / 3) * 2;
        }
    }
}

var integerBreak = function(n) {
    if (n <= 3) return n - 1;
    
    let quotient = Math.floor(n / 3);
    let remainder = n % 3;
    
    if (remainder === 0) {
        return Math.pow(3, quotient);
    } else if (remainder === 1) {
        return Math.pow(3, quotient - 1) * 4;
    } else {
        return Math.pow(3, quotient) * 2;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
数学方法O(log n)O(1)
动态规划O(n²)O(n)

推荐使用数学方法，时间和空间复杂度都更优。

相关题目