友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
思路分析
-
一刷
-
二刷
-
三刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Integer Break.
* Memory Usage: 38.1 MB, less than 14.29% of Java online submissions for Integer Break.
*
* Copy from: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/[面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解） - 剪绳子 - 力扣（LeetCode）]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-04-26 16:38
*/
public int integerBreak(int n) {
if (n < 2) {
return 0;
}
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
int timeOf3 = n / 3;
int mod = n % 3;
if (mod == 0) {
return (int) Math.pow(3, timeOf3);
}
if (mod == 1) {
return (int) Math.pow(3, timeOf3 - 1) * (3 + 1);
}
return (int) Math.pow(3, timeOf3) * 2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-13 16:08:50
*/
public int integerBreak(int n) {
// 1. 确定 dp 数组（dp table）以及下标的含义
// dp[i] 表示 i 值被拆分后最大乘积数
// 3. dp 数组，默认就是0， 0、1拆分后最大乘积就是0，无需初始化
int[] dp = new int[n + 1];
// 4. 确定遍历顺序，从 1 → n/2 + 1 逐个遍历
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i / 2 + 1; j++) {
// 2. 确定递推公式: dp[i] = max(j*(i-j), j * dp[i - j])
dp[i] = Math.max(Math.max(j * (i - j), j * dp[i - j]), dp[i]);
}
}
return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-15 20:47:03
*/
public int integerBreak(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) {
int max = -1;
for (int j = 1; j < i / 2 + 1; j++) {
max = Math.max(Math.max(max, j * (i - j)), j * dp[i - j]);
}
dp[i] = max;
}
return dp[n];
}