阅读量:0
目录
力扣题号：343. 整数拆分 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
如果你看完还不会，请看下图：
题目描述
给定一个正整数 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
思路
解法一：动态规划
那么其实这道题的思路就难一点了，但是可以使用动态规划的思路来写，还是很容易发现这个点的。
（1）dp数组的下标及其含义
我们这里的dp[i]就是指拆当前i这个数得到的最大乘积
我们是从较小的i逐步递推到我们的目标n这个数的，所以循环是慢慢推过去的。
（2）确定递推公式
一个数n，可以拆成两个数就是i和i-j,那么就是
但是，例如10可以拆分成3*3*4，那么这时候，我们就不只是需要拆分成两个数了，还需要多个数，不知道是多少，但是肯定是存在的。这时候我们的公式就是
那么其实我们要找的是最大的，因此还需要取最大值，但是还没完，因为你拆分之后你并不知道，这次的拆法会不会比之前的拆法大，所以你应该将dp[i]也加入比较然后取最大值,如下：
（3）初始化递推数组
在我们这里的话，我们可以先想想，0和1的拆分能拆吗，有意义吗，显然是没有的，因此直接给一个0，让他很小就行了，因为我们要取的是最大值，所以并不影响最终的答案。但是2就有了意义，所以初始化应该是这样：
这样我们的i就可以从3开始遍历了。
（4）确定遍历顺序
思路都如此明确了，我们要得到n这个数的最大值，那么就需要之前的数来推出得到，所以这里显然是从小到大来进行遍历了。
（5）根据题意推出dp数组对照
例如到10
[0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36]
代码实现
class Solution { public int integerBreak(int n) { // 确定好dp数组的下标及其含义 // 我们这里的dp[i]就是指拆当前i这个数得到的最大乘积 // 我们是从较小的i逐步递推到我们的目标n这个数的 // 确定递推公式 // 一个数n，可以拆成两个数就是i和i-j // 也可以拆分成多个数，也就是i 和 dp[i-j] // 这里的dp[i-j]也就是将i-j也进行了拆分得到了最大的 // dp[i]=Math.max(j*(i-j),j*dp[i-j]) int[] dp = new int[n+1]; // 初始化dp数组,0,1,没有意义,2就有了 dp[0]=0; dp[1]=0; dp[2]=1; for(int i = 3;i <= n; i++){ for(int j = 1; j < i; j++){ dp[i]=Math.max(Math.max(j*(i-j),j*dp[i-j]),dp[i]); } } return dp[n]; } }
这咋还没有打败全世界的人！！！！！！！！！！！！
这里还是有一个优化的方法的，你通过观察不难发现，要想让这个乘积最大，这些数都是几乎近似的数，差值基本上在1左右，所以其实我们的j做了很多的多余操作，后面的一半都不用继续寻找了，只要前半段就可以了。
class Solution { public int integerBreak(int n) { // 确定好dp数组的下标及其含义 // 我们这里的dp[i]就是指拆当前i这个数得到的最大乘积 // 我们是从较小的i逐步递推到我们的目标n这个数的 // 确定递推公式 // 一个数n，可以拆成两个数就是i和i-j // 也可以拆分成多个数，也就是i 和 dp[i-j] // 这里的dp[i-j]也就是将i-j也进行了拆分得到了最大的 // dp[i]=Math.max(j*(i-j),j*dp[i-j]) int[] dp = new int[n+1]; // 初始化dp数组,0,1,没有意义,2就有了 dp[0]=0; dp[1]=0; dp[2]=1; for(int i = 3;i <= n; i++){ for(int j = 1; j <= i/2; j++){ dp[i]=Math.max(Math.max(j*(i-j),j*dp[i-j]),dp[i]); } } return dp[n]; } }
快到起飞！！！！
解法二：贪心算法（已更新）
后续更新另一篇文章，对我就是在水文章
总结
EZ，收徒
开玩笑，大家喜欢的话点个赞吧~~~谢谢啦
ヾ(￣▽￣)Bye~Bye~
