343. 整数拆分
343. 整数拆分
分析
回溯
这个题可以先分段然后回溯，求出所有的可能性然后求最大值
但是 n 最大是 58，也就是说，可能要递归 58 层，效率可想而知会有多慢。
数学分析 - 贪心
对于这种跟数论有点相关的题目，一定要尝试推演，然后观察。
1*1 = 1但是1+1 = 2，不拆分比拆分得到的结果大2*2 = 4但是2+2 = 4，不拆分跟拆分得到的结果一样3*3 = 9但是3+3 = 6，拆分比不拆分得到的结果大。也就是说拆分 6，比直接乘以 6 得到的结果要更大
也就是说，只要一个数字是 >=4 的，拆分之后再相乘都比直接相乘得到的结果要大，举个例子：直接乘以 5，没有乘以 2*3=6 的结果大。
所以最大的乘积，一定是全部换成了 2 和 3，我们直接计算 n 可以刚好换成多少个 2 和 3 即可，注意是刚好，不能有余数，如果余数是 1(也只能是 1)，与 1 相乘没有增加乘积，就相当于浪费了一位数字。而且应该是尽量多换成 3，举个例子 6，6 可以换成两个 3 和三个 2，但是 3*3=9 比 2*2*2=8 要大，所以尽量换成 3 也是一种贪心，这个贪心跟 860. 柠檬水找零 中兑换 20 块钱的时候优先使用 10 块钱是一样的。
如何计算 n 刚好能换成多少个 2 和 3 呢。很简单
- 先除以 3 ，记录结果
- 算一下除以 3 的余数
- 剩余 1 ，就将一个 3 加上这个 1，变成 4 拆分成两个 2，
- 如果剩余 2，那就直接换成一个 2，
- 根据 3 的数量累乘 3
- 根据 2 的数量累乘 2
效率最高。
动态规划
将 dp[i] 数组定义为，i 拆分成多个正整数之后，其乘积最大值。
如何求 dp[i] 呢？用 for 循环循环所有一个数乘以另一个数的情况，i 拆分出的两个数为 j 和 i-j，然后比较 j*(i-j) 跟 j*dp[i-j] 哪个更大，j*(i-j) 表示只将 i 拆分成两个数，而 j*dp[i-j] 表示将拆分成更多的数，为什么不是拆分成 dp[j]*dp[i-j]，其实因为 j 是从 1 到 i-1，所以 j 实际上是已经把所有的情况都考虑在内了，比如 i 等于 10，当前 j 为 6，j 可以拆分成 2 和 4 ，那么当前应该计算 2*4*dp[4] ,但是因为 j 是从 1 开始遍历的，所以实际上我们已经遍历过了 j=2 和 j=4 的情况，j=2 时候，另一半为 dp[8]，j=4 时候，另一半为 dp[6]，这些乘积的大小我们前面也都比较过，也就是说，j 拆分与 j 不拆分的情况我们都已经对比过了。所以不会有问题。这一点确实有点不好理解。
我想出来的思路只用了一个 for 循环，这个标准方法用了 for 循环嵌套，所以效率会不高。但是上面这个思路确实是将一个问题变成了一个嵌套的子问题。这是解决动态规划问题的基本思路。
一开始我拒绝使用两层 for 循环的思路，其实用两层 for 循环也可以，不是用两层就代表不行。
解题
数论解法
class Solution {
public int integerBreak(int n) {
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
// 从 4 开始处理
int count3 = 0;
int count2 = 0;
count3 = n / 3;
int left = n % 3;
if (left == 1) {
count3--;
count2 = 2;
} else if (left == 2) {
count2 = 1;
}
int result = 1;
for (int i = 0; i < count3; i++) {
result *= 3;
}
for (int i = 0; i < count2; i++) {
result *= 2;
}
return result;
}
}
动态规划
public int integerBreak(int n) {
int[] dp = new int[n + 1];
// n从2开始
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
// 至少要拆分出1
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}