力扣打卡:343. 整数拆分
解题思路
可能思路不是很好想到
- 大于1的每一个数至少分成
1 + n-1
|2 + n-2
|...
- 根据上面的分解,每一个大于1的数都可以分解成至少两个整数,那么这两个分解生成的两个整数如果同样属于大于1的这个范围
- 那么可以继续分解,此时每一个数都可以分解成 2个 或者 n个 的数字的和
- 如果从两个开始分,2,3,4,5,6 …分解下去,总是能找到乘积最大的时候
流程
- 函数先分解成两个数
for(int i=1; i<n; i++)
,1+n-1
|2+n-2
等等 - 定义一个函数,能得到这个数的各种分解中的最大乘积
int subAns = planA(n-i)
- 这个最大的乘积和当前这个数进行比较,选择较大的一个
int subMax = Math.max(n-i, subAns)
- 记录下 选择出来的较大值 和 两个数的各种分解中的分解的较大值, 取较大的值
max = Math.max(max, i * subMax);
- 最后返回这个较大的值即可
举个例子
给定一个数 10
- 这个数可以按照两个数的分解:分解成
1 + 9 | 2 + 8 | 3 + 7 | 4 + 6 | 5 + 5 | 6 + 4 | 7 + 3 等等
- 此时每一个大于
1
的数字又可以进行分解成两个数,i + n-i
i 从1
开始,那么到最后一定可以分解到各种组合 - 写递归函数,弄清楚递归函数的定义,然后将这个定义给出的结果进行使用,然后联系当前状态和子状态,最后返回就可以得到结果了
- 定义一个函数,可以得到每一个数的各种分解中的最大乘积(注意:一般题目要求的就是我们需要定义递归函数的返回)
- 第一次得到
9
的各种分解的最大乘积值,与9
进行比较,取大值subMax
,不一定是各种分解中的最大值,不分解可能更大,取大值即可 - 然后与初始的
max
进行 取大值的比较Math.max(max, i * subMax)
,注意此时的是i * subMax
,此时的max记录大值 - 第二次得到
8
的各种分解的最大乘积值,与8
进行比较,取大值subMax
,不一定是各种分解中的最大值,不分解可能更大,取大值即可 - 然后与
9
的最大乘积值进行比较,取大值即可 - 依次类推,能够这样分解的愿意就在于分解成两个数之后,还可以再进行分解,这个也是这个题目难理解的地方
- 只要理解清楚了,和平常的题目就一样,写出了暴力递归,那么自顶向下的动态规划,也就是多了判断和记录的两个过程
代码
class Solution {
public int integerBreak(int n) {
// 理解原理: 每一个数都可以分解成 1 + n-1 | 2 + n-2 | 3 + n-3 ....
// 同时这其中的n-1,n-2,n-3又可以重新分为小于其的最大整数和1,依次类推
// 需要考虑的是:这些数可以一直分解,直至小于2时,不能分解成两个整数的和了,那么停止
// 也就是说
// 这也就是说明了,只需要考虑两个数的情况就可以了,不需要考虑分解成三个或者是分解成四个这种场景
// 因为每个数分解成两个数之后,这两个数的又可以分解成两个数,然后再次分解成两个数,最后在范围内的分解都存在
// 那么定义一个函数,能够得到给定的数的最大乘积
// return planA(n);
int[] memo = new int[n+1]; // 需要n+1的长度进行储存数据n
return planB(n, memo);
}
public int planA(int n){
if(n < 2) return 0; // 当 n 已经小于 2, 此时不能再进行分解了, 也就是返回0
int max = 0; // 初始化为0
for(int i=1; i<n; i++){
int subAns = planA(n-i);
int subMax = Math.max(n-i, subAns);
max = Math.max(max, i * subMax);
}
return max;
}
// 写出了暴力递归的方式,那么自顶向下的动态规划也就是多了判断和记录的两个过程
public int planB(int n, int[] memo){
if(n < 2) return 0; // 如果此时的n小于2,那么不能再进行分解了
if(memo[n] != 0) return memo[n];
int max = 0;
for(int i=1; i<n; i++){
int subAns = planB(n-i, memo);
int subMax = Math.max(n-i, subAns); // 这里的意思是指: n-i 的大小 和 n-i 分解成某一些数字后的乘积的大小的对比
max = Math.max(max, i * subMax);
}
memo[n] = max;
return memo[n];
}
}