做网站想要个计算器功能,泰安网红餐厅,免费网站后台管理系统模板,物流网站建设方案权限管理【力扣】343. 整数拆分
给定一个正整数 n #xff0c;将其拆分为 k 个 正整数 的和#xff08; k 2 #xff09;#xff0c;并使这些整数的乘积最大化。返回可以获得的最大乘积 。
示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。
示例 2: 输入: n 10 输出:…【力扣】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
题解
动态规划 确定 dp 数组以及下标的含义 dp[i]分拆数字 i可以得到的最大乘积为 dp[i]。 确定递推公式 有两种渠道得到 dp[i]. 一个是 j * (i - j) 直接相乘。(2个) 一个是 j * dp[i - j]相当于是拆分 (i - j) 3个及3个以上 递推公式dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j)); dp 数组如何初始化 dp[0]dp[1] 就不应该初始化也就是没有意义的数值。 dp[2] 1 确定遍历顺序 dp[i] 是依靠 dp[i - j] 的状态所以遍历 i 一定是从前向后遍历先有 dp[i - j] 再有dp[i]
for (int i 3; i n ; i) {// 从1开始的。从0开始的话那么让拆分一个数拆个0求最大乘积就没有意义for (int j 1; j i - 1; j) {dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));}
}优化
for (int i 3; i n ; i) {for (int j 1; j i / 2; j) {dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));}
}举例推导 dp 数组打印 dp 数组 public static int integerBreak(int n) {//dp[i] 为正整数 i 拆分后的结果的最大乘积int[] dp new int[n1];dp[2] 1;for(int i 3; i n; i) {for(int j 1; j i-j; j) {// 这里的 j 其实最大值为 i-j,再大只不过是重复而已//并且在本题中我们分析 dp[0], dp[1]都是无意义的//j 最大到 i-j,就不会用到 dp[0]与dp[1]dp[i] Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j 再相乘//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。}}return dp[n];}数学
public static int integerBreak2(int n) {if (n 3) {return n - 1;}int quotient n / 3;int remainder n % 3;if (remainder 0) {return (int) Math.pow(3, quotient);} else if (remainder 1) {return (int) Math.pow(3, quotient - 1) * 4;} else {return (int) Math.pow(3, quotient) * 2;}
}
