Article / 文章
LeetCode 第343题：整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
📖 文章摘要
本文详细解析LeetCode第343题“整数拆分”，这是一道中等难度的动态规划题目。文章提供了动态规划和数学方法两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升动态规划和数学思维能力的程序员。
核心知识点： 动态规划、数学、贪心算法
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升动态规划能力的开发者
题目描述
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1示例 2：
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36提示
- 2 <= n <= 58
解题思路
方法一：动态规划
使用动态规划求解最优拆分方案。
关键点：
- 定义dp[i]表示整数i拆分后的最大乘积
- 考虑所有可能的拆分方案
- 状态转移方程：dp[i] = max(dp[i], max(j * (i-j), j * dp[i-j]))
具体步骤：
- 创建dp数组
- 初始化dp[2] = 1
- 遍历每个数字i
- 对每个i，遍历所有可能的拆分点j
- 更新dp[i]为最大值
时间复杂度：O(n^2) 空间复杂度：O(n)
方法二：数学方法
通过数学分析可知，尽可能多地使用3进行拆分可以得到最大乘积。
关键点：
- 尽可能拆分出3
- 最后剩余4时不再拆分
- 处理特殊情况2和3
具体步骤：
- 处理特殊情况n=2和n=3
- 计算可以拆分出多少个3
- 处理余数情况
时间复杂度：O(1) 空间复杂度：O(1)
图解思路
动态规划分析表
| 数字n | 最优拆分 | 最大乘积 | 计算过程 |
|---|---|---|---|
| 2 | 1+1 | 1 | 1×1=1 |
| 3 | 1+2 | 2 | 1×2=2 |
| 4 | 2+2 | 4 | 2×2=4 |
| 5 | 2+3 | 6 | 2×3=6 |
| 6 | 3+3 | 9 | 3×3=9 |
| 7 | 3+4 | 12 | 3×4=12 |
数学方法分析
规律总结：
1. n=2: 1×1=1
2. n=3: 1×2=2
3. n=4: 2×2=4
4. n>4: 尽可能多地拆分出3
例如：10 = 3 + 3 + 4
3×3×4 = 36 > 3×3×3×1 = 27代码实现
C# 实现
public class Solution {
// 方法一：动态规划
public int IntegerBreak(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.Max(dp[i], Math.Max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
// 方法二：数学方法
public int IntegerBreakMath(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
int quotient = n / 3;
int remainder = n % 3;
if (remainder == 0) {
return (int)Math.Pow(3, quotient);
} else if (remainder == 1) {
return (int)Math.Pow(3, quotient - 1) * 4;
} else {
return (int)Math.Pow(3, quotient) * 2;
}
}
}Python 实现
class Solution:
# 方法一：动态规划
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[2] = 1
for i in range(3, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
return dp[n]
# 方法二：数学方法
def integerBreakMath(self, n: int) -> int:
if n == 2:
return 1
if n == 3:
return 2
quotient = n // 3
remainder = n % 3
if remainder == 0:
return 3 ** quotient
elif remainder == 1:
return 3 ** (quotient - 1) * 4
else:
return 3 ** quotient * 2C++ 实现
class Solution {
public:
// 方法一：动态规划
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
// 方法二：数学方法
int integerBreakMath(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
int quotient = n / 3;
int remainder = n % 3;
if (remainder == 0) {
return pow(3, quotient);
} else if (remainder == 1) {
return pow(3, quotient - 1) * 4;
} else {
return pow(3, quotient) * 2;
}
}
};执行结果
C# 实现
- 执行用时：24 ms
- 内存消耗：25.1 MB
Python 实现
- 执行用时：32 ms
- 内存消耗：14.9 MB
C++ 实现
- 执行用时：0 ms
- 内存消耗：6.1 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 24 ms | 25.1 MB | 代码结构清晰 |
| Python | 32 ms | 14.9 MB | 实现简洁 |
| C++ | 0 ms | 6.1 MB | 性能最优 |
代码亮点
- 🎯 动态规划思路清晰
- 💡 数学方法高效
- 🔍 边界条件处理完善
- 🎨 代码简洁优雅
常见错误分析
- 🚫 忘记处理特殊情况n=2和n=3
- 🚫 动态规划初始化错误
- 🚫 数学方法中的余数处理错误
- 🚫 整数溢出问题
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 动态规划 | O(n^2) | O(n) | 通用性强 | 效率较低 |
| 数学方法 | O(1) | O(1) | 高效 | 不易理解 |
相关题目
- LeetCode 279. 完全平方数 - 中等
- LeetCode 91. 解码方法 - 中等
- LeetCode 96. 不同的二叉搜索树 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第343题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！