嵩明网站建设,深圳食品网站建设,wordpress悬浮按钮,做网站 接活343. 整数拆分
给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n 2
输出: 1
解释: 2 1 1, 1 1 1。示例 2:
输入: n 10
输出: 36…343. 整数拆分
给定一个正整数 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
思路(动态规划)
法一
对于正整数 n当 n ≥ 2 时可以拆分成至少两个正整数的和。令 x 是拆分出的第一个正整数则剩下的部分是 n − xn − x 可以不继续拆分或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积因此可以使用动态规划求解。
创建数组 dp其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后这些正整数的最大乘积。特别地0 不是正整数1 是最小的正整数0 和 1 都不能拆分因此 dp[0] dp[1] 0。
当 i ≥ 2 时假设对正整数 i 拆分出的第一个正整数是 j1 ≤ j i则有以下两种方案
将 i 拆分成 j 和 i − j 的和且 i − j 不再拆分成多个正整数此时的乘积是 j × (i − j)将 i 拆分成 j 和 i − j 的和且 i − j 继续拆分成多个正整数此时的乘积是 j × dp[i − j]。
因此当 j 固定时有 dp[i] max(j × (i − j), j × dp[i − j])。由于 j 的取值范围是 1 到 i − 1需要遍历所有的 jjj 得到 dp[i] 的最大值因此可以得到状态转移方程如下
dp[i]max1≤ji{max(j×(i−j),j×dp[i−j])}d p[i]\max _{1 \leq ji}\{\max (j \times(i-j), j \times d p[i-j])\} dp[i]1≤jimax{max(j×(i−j),j×dp[i−j])}
最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后这些正整数的最大乘积。
法二
由于分解成正整数的乘积最大若分解的正整数有1不会使乘积变大所以分解的正整数大于等于2
又至少分解2个正整数当 n 2,或 n 3 时最大的乘积分别为1和2n 4 时分解的最小整数为2否则只会变小
举一些栗子
4 2 2 2 * 2 4
5 2 3 2 * 3 6
6 3 3 3 * 3 9
7 2 2 3 2 5
8 2 3 3 2 6
9 4 2 3 2 7
10 3 3 4 3 7创建数组 dp其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后这些正整数的最大乘积。由以上可知分解的都可表示为 2 或 3 与另一个数 j最大乘积就是2 或 3 乘以另一个数的最大乘积dp[j].
代码:(Java)
法一
public class IntegerBreak {public static void main(String[] args) {// TODO Auto-generated method stubint n 10;System.out.println(integerBreak(n));}int[] dp new int[n 1];dp[1] 1;for (int i 2; i n; i) {for (int j 1; j i - 1; j) {dp[i] Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));}}return dp[n];
}法二
public class IntegerBreak {public static void main(String[] args) {// TODO Auto-generated method stubint n 10;System.out.println(integerBreak(n));}public static int integerBreak(int n) {if(n / 2 2) {return n - 1;}int[] dp new int[n 1];dp[2] 2;dp[3] 3;for(int i 4; i n; i) {dp[i] Math.max(2*dp[i-2], 3*dp[i-3]);}return dp[n];}
}运行结果 复杂度分析
时间复杂度O(n2)O(n^2)O(n2)其中 n 是给定的正整数。对于从 2 到 n 的每一个整数都要计算对应的 dp 值计算一个整数对应的 dp 值需要 O(n) 的时间复杂度因此总时间复杂度是 O(n2)。(法二时间复杂度为O(n))
空间复杂度O(n)其中 n 是给定的正整数。创建一个数组 dp其长度为 n1
注仅供学习参考
题目来源力扣。
