第九章动态规划——整数拆分_电脑知识

第九章动态规划——整数拆分

创始人

2024-12-13 02:04:18

力扣题号：343. 整数拆分 - 力扣（LeetCode）

题目描述

示例 1:

示例 2:

提示:

思路

解法一：动态规划

（1）dp数组的下标及其含义

（2）确定递推公式

（3）初始化递推数组

（4）确定遍历顺序

（5）根据题意推出dp数组对照

代码实现

解法二：贪心算法（已更新）

总结

力扣题号：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,那么就是

$j\times(i-j)$

但是，例如10可以拆分成3*3*4，那么这时候，我们就不只是需要拆分成两个数了，还需要多个数，不知道是多少，但是肯定是存在的。这时候我们的公式就是

$j\times dp[i-j]$

那么其实我们要找的是最大的，因此还需要取最大值，但是还没完，因为你拆分之后你并不知道，这次的拆法会不会比之前的拆法大，所以你应该将dp[i]也加入比较然后取最大值,如下：

$dp[i]=max(j\times(i-j),j\times dp[i-j],dp[i])$

（3）初始化递推数组

在我们这里的话，我们可以先想想，0和1的拆分能拆吗，有意义吗，显然是没有的，因此直接给一个0，让他很小就行了，因为我们要取的是最大值，所以并不影响最终的答案。但是2就有了意义，所以初始化应该是这样：

dp[0]=0;

dp[1]=0;

dp[2]=1;

这样我们的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];     } }