LeetCode 343. 整数拆分

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 343. 整数拆分

思路分析

解法一：贪心（推荐）

核心思路：

数学结论：将 n 尽可能地拆成多个 3 的和，乘积最大。

当余数为 0 时，直接用 3 的幂次；当余数为 1 时，用一个 4（即 2×2）代替 3+1；当余数为 2 时，多乘一个 2。

原因：2+2+2 > 3+3 对应乘积 8 < 9 不成立，但 3+3 > 2+2+2 即 9 > 8；而 1+3 < 2+2 即 4 < 4 不成立，因此余数为 1 时把最后的 3+1=4 换成 2+2=4，乘积由 3×1=3 变为 2×2=4，更优。

复杂度分析：

时间复杂度：O(1)，仅做常数次数学运算。

空间复杂度：O(1)，无额外空间占用。

class Solution {
    public int integerBreak(int n) {
        // 特殊情况：n=2 只能拆成 1+1，乘积为 1；n=3 只能拆成 1+2，乘积为 2
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int quotient = n / 3;
        int remainder = n % 3;

        // 余数为 0：全部拆成 3
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }

        // 余数为 1：最后的 3+1 换成 2+2，乘积更大
        if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        }

        // 余数为 2：多乘一个 2
        return (int) Math.pow(3, quotient) * 2;
    }
}

func integerBreak(n int) int {
    // 特殊情况：n=2 只能拆成 1+1，乘积为 1；n=3 只能拆成 1+2，乘积为 2
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }

    quotient := n / 3
    remainder := n % 3

    // 余数为 0：全部拆成 3
    if remainder == 0 {
        return pow(3, quotient)
    }

    // 余数为 1：最后的 3+1 换成 2+2，乘积更大
    if remainder == 1 {
        return pow(3, quotient-1) * 4
    }

    // 余数为 2：多乘一个 2
    return pow(3, quotient) * 2
}

func pow(base, exp int) int {
    result := 1
    for i := 0; i < exp; i++ {
        result *= base
    }
    return result
}

解法二：动态规划

核心思路：

定义 dp[i] 为将正整数 i 拆分后所能得到的最大乘积。

对于每个 i，枚举第一段拆出的数 j（1 ≤ j < i），剩余部分 i-j 可以不再拆（直接取 i-j）或继续拆（取 dp[i-j]）。

状态转移：dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]))

初始值：dp[1] = 1，从 i=2 开始递推。

复杂度分析：

时间复杂度：O(n²)，其中 n 为输入整数，外层枚举 i，内层枚举拆分点 j。

空间复杂度：O(n)，其中 n 为输入整数，需要长度为 n+1 的 dp 数组。

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // j*(i-j)：将 i 拆成 j 和 i-j，i-j 不再继续拆
                // j*dp[i-j]：将 i 拆成 j 和 i-j，i-j 继续拆
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

func integerBreak(n int) int {
    dp := make([]int, n+1)
    dp[1] = 1

    for i := 2; i <= n; i++ {
        for j := 1; j < i; j++ {
            // j*(i-j)：将 i 拆成 j 和 i-j，i-j 不再继续拆
            // j*dp[i-j]：将 i 拆成 j 和 i-j，i-j 继续拆
            dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]))
        }
    }

    return dp[n]
}

相似题目

题目	难度	考察点
279. 完全平方数	中等	动态规划 / BFS
322. 零钱兑换	中等	动态规划 / 完全背包
139. 单词拆分	中等	动态规划 / 字符串分割
198. 打家劫舍	中等	动态规划 / 线性 DP
338. 比特位计数	简单	动态规划 / 位运算
96. 不同的二叉搜索树	中等	动态规划 / 卡特兰数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/63992688