摘要

在开发过程中，我们经常会遇到资源切分、任务拆解等问题，其中一个常见的优化目标是“如何拆得最合理以获得最大收益”。LeetCode 343 这道题就模拟了类似场景：把一个整数拆成多个正整数的和，使得它们的乘积最大。看似数学题，其实也挺有意思的编程思路在里面。这篇文章我们就来用 Swift 一步步拆解思路，并跑通一套可运行的代码 Demo。

描述

题目非常直白：给定一个正整数 n，你要把它拆成至少两个正整数的和，然后让这些数的乘积最大。返回你能得到的这个最大乘积。

题目要求：

• n 必须拆成两个或两个以上的正整数之和。
• 求这些数乘积的最大值。

示例：

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 乘积为 1 × 1 = 1

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 乘积为 3 × 3 × 4 = 36

题解答案

这道题其实有两个方向可以考虑：

1. 动态规划（DP）解法：记录每个数的最大拆分乘积。
2. 数学贪心解法：把尽可能多的 3 拆出来能得到最大乘积。

因为 n <= 58，所以 DP 和贪心都能很快跑出来。下面我们先看 DP，再对比贪心优化。

题解代码分析

方法一：动态规划

func integerBreak(_ n: Int) -> Int {
    if n <= 2 { return 1 }

    var dp = [Int](repeating: 0, count: n + 1)
    dp[1] = 1

    for i in 2...n {
        for j in 1..<i {
            // 取两种情况的最大值：
            // 1. 拆成 j 和 i-j（不再继续拆分 i-j）
            // 2. 拆成 j 和 dp[i-j]（继续拆分 i-j）
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        }
    }

    return dp[n]
}

方法二：数学贪心（推荐解法）

func integerBreak(_ n: Int) -> Int {
    if n == 2 { return 1 }
    if n == 3 { return 2 }

    var n = n
    var result = 1

    while n > 4 {
        result *= 3
        n -= 3
    }

    return result * n
}

哪个更好？

• 如果你是在刷题、面试阶段，建议先写 DP，清晰易懂。
• 如果你做性能优化或数学竞赛，贪心解法会更高效，而且逻辑更精妙。

示例测试及结果

我们用几组数据测试一下上面的函数：

print(integerBreak(2))  // 输出：1
print(integerBreak(10)) // 输出：36
print(integerBreak(8))  // 输出：18，拆成 3+3+2
print(integerBreak(5))  // 输出：6，拆成 2+3

输出结果如下：

1
36
18
6

没问题，结果都跟预期一致。

时间复杂度

动态规划解法：

• 时间复杂度：O(n^2)，两层循环。
• 空间复杂度：O(n)，只用了一个数组记录状态。

数学贪心解法：

• 时间复杂度：O(n)，最坏情况每次减去 3。
• 空间复杂度：O(1)，只用了几个变量。

空间复杂度

如上所述：

• 动态规划：需要 O(n) 空间维护数组。
• 数学贪心：只用常数空间。

总结

这题其实不只是算法问题，更像是一个资源优化策略问题。在实际开发中，比如你要把预算、时间、服务器资源拆分成多个任务或服务节点时，如何“拆得合理”才能“赚得最多”，就是这类思想的体现。

两种解法各有优劣：

• 想练手算法、打基础，用动态规划。
• 想理解原理、提高效率，用数学贪心。

多练几次类似的题，数学感知和拆解思路都会跟着提升。希望这篇文章能帮你吃透这道题，如果喜欢这类题解，也欢迎点赞收藏分享给小伙伴 😄！