343. 整数拆分 | 暴力求解 | 暴力递归 | 动态规划 | 自顶向下分析
2021/12/16 23:41:56
本文主要是介绍343. 整数拆分 | 暴力求解 | 暴力递归 | 动态规划 | 自顶向下分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
力扣打卡: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]; } }
这篇关于343. 整数拆分 | 暴力求解 | 暴力递归 | 动态规划 | 自顶向下分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据
- 2024-05-22通过通配符过滤数据
- 2024-05-22字段的拼接与计算
- 2024-05-22聚合函数