参考文章：代码随想录https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html
一、题目
给定一个正整数 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-break
二、题解
方法一：动态规划
利用动规五部曲，分析如下：
- 确定 dp 数组以及下标的含义
dp[i]：拆分数字 i，可以得到的最大乘积为 dp[i]。
- 确定递推公式
可以想 dp[i] 最大乘积是怎么得到的呢？
其实可以从 1 遍历 j，然后有两种渠道得到 dp[i]：
-
一个是 j * (i – j) 直接相乘
-
一个是 j * dp[i – j]，相当于是拆分 (i – j)，对这个拆分不理解的话，可以回想 dp 数组的定义。
不拆分 j 是因为 j (i – j) 是单纯的把整数拆分为两个数相乘，而 j dp[i – j] 是拆分成两个以及两个以上的个数相乘。如果定义 dp[i – j] * dp[j] 则是默认将一个数强制拆成 4 个以及 4 个以上了。
所以递推公式为：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j})
那么在取最大值的时候，为什么还要比较 dp[i] 呢？
因为 j 从 1 到 i – 1，每一个 j 都对应了一个 dp[i]，(i – j) j 和 dp[i – j] j 比较取最大值后还得与上一个 j 对应的 dp[i] 比较再取最大值，才能保证 dp[i] 始终为最大值。
- dp 的初始化
从 dp[i] 的定义来说，dp[0]、dp[1] 就不应该初始化。拆分 0 和拆分 1 的最大乘积是多少？这是没有意义的数值。
所以只初始化 dp[2] = 1 即可
- 确定遍历顺序
由递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)) 可知：
dp[i] 是依靠 dp[i – j] 的状态，所以遍历 i 一定是从前向后遍历，先有 dp[i – j] 再有 dp[i]。
注意 枚举 j 的时候，是从 1 开始的。从 0 开始的话，那么让拆分 0 求最大乘积就没有意义了。
j 的结束条件是 j < i – 1 ，其实 j < i 也是可以的，不过可以节省一步，例如让 j = i – 1 的话，其实在 j = 1 的时候，这一步就已经拆出来了，重复计算，所以 j < i – 1 即可
更优化一步，可以让 j < i – j，也就是 j <= i / 2 即可：
因为拆分一个数 n 使之乘积最大，那么一定是拆分成 m 个近似相同的子数相乘才是最大的。例如 6 拆成 3 3， 10 拆成 3 3 * 4。 100 的话也是拆成 m 个近似数组的子数相乘才是最大的。只不过我们不知道 m 究竟是多少而已，但可以明确的是 m 一定大于等于 2，拿最差也应该是拆成两个相同的可能是最大值。
那么 j 遍历，只需要遍历到 n / 2 就可以，后面就没有必要遍历了，一定不是最大值。
- 举例推导 dp 数组
举例当 n 为 10 的时候，dp 数组里的数值为：[0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36]
方法二：贪心 / 数学方法
根据数学的证明，当 n >= 5 时，尽可能多的拆出 3，剩下的如果剩下 4，则拆成 2 + 2，这样乘积最大。
所以可能数学的规律是：当 n > 4时，尽可能拆分成 3 的倍数，余数为 0 的话全 3，余数为 1 的话拿一个 3 加上 1 组成 4 拆成两个 2（因为 3 + 1 不如 2 + 2），余数为 2 的话拆成一个 2 和剩下的 3。
所以通过数学分析，发现将整数尽可能拆分为多个 3 时乘积最大。具体规则如下：
- 当 n <= 3 时，返回 n – 1（必须拆分为至少两个数）。
- 当 n > 3 时：
- 如果余数为 0，最大乘积为 3 的幂次。
- 如果余数为 1，将其中一个 3 和 1 替换为 2 和 2（因为 3 × 1 < 2 × 2）。
- 如果余数为 2，直接乘以 2。
在 Java 中，计算 3^a^ 可能需要用 Math.pow 方法，但是可能有一些问题。
首先当 a 很大的时候 3^a^ 可能超出整数范围？本题中的 n 最大是 58，而 58 / 3 = 19，58 % 3 = 1，此时要计算 3^18^ * 4，而 3^18^ * 4 = 1549681956 小于 2^31^ – 1 即 2147483647，所以没超过 Integer 的范围，用 int 是可以的。
第二个问题，Math.pow 返回的是 double 类型，转换成 int 可能会有精度问题。因为 double 类型只能精确表示 2 的幂次，对于 3 的较大幂次计算如 3^19^，用 Math.pow 可能会有精度丢失。所以为了避免使用 Math.pow 的精度问题，应该用循环相乘来手动计算乘积，这样可能更可靠。
以上内容对应代码中的写法二，整理自 DeepSeek 的回答，更详细一点。
写法一来自 carl 哥，和写法一差不多，但优化了一下更巧妙一些。直接用的贪心，每次拆成 n 个 3，如果剩下是 4，则保留 4，然后相乘，但是这个结论需要数学证明其合理性！
另外从 n = 10 时 dp 数组的值也可看出：从下标 5 开始，dp[i] 一定是 3 的倍数
总结：
这道题的解法有两种，一种是数学方法，利用尽可能多的 3 拆分；另一种是动态规划。
- 数学方法通过分析数的拆分规律，高效地计算出结果，时间复杂度为 O(n)。
- 动态规划方法通过递推计算每个整数的最优拆分，时间复杂度为 O(n²)，适用于较小的 n。
数学方法的代码更简洁，运行时间更快。所以应该优先选择数学方法。
两种方法均能正确解决问题都是可行的。数学解法更高效在效率上更优，但动态规划解法更直观更容易想到，特别是当数学规律不明确的时候。
三、代码
方法一
public class T343 {
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++) {
// for (int j = 1; j <= i / 2; j++) {
for (int j = 1; j <= i - j; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}方法二
写法一：
public class T343 {
public int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int result = 1;
while (n > 4) {
result *= 3;
n -= 3;
}
result *= n;
return result;
}
}写法二：
class T343 {
public int integerBreak(int n) {
if (n <= 3) {
return n - 1;
}
int a = n / 3;
int b = n % 3;
if (b == 0) {
return pow(3, a);
} else if (b == 1) {
return pow(3, a - 1) * 4;
} else {
return pow(3, a) * 2;
}
}
private int pow(int base, int exponent) {
int result = 1;
for (int i = 0; i < exponent; i++) {
result *= base;
}
return result;
}
}