343、整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
题解
1、暴力深度优先搜索
$F(n) = \max(i*F(n-i)),i = 1,2,3…n-1$
- 代码
// java
class Solution {
public int integerbreak(int n) {
// 递归结果
if (n == 2) {
return 1;
}
int res = -1;
// 迭代求最大值
for (int i = 1;i < n;i++) {
res = Math.max(res, Math.max(i*(n-i),i*integerBreak(n-i)));
}
return res;
}
}
2、记忆化深度优先搜索
- 又称为自顶而上的动态规划
- 代码
// java
class Solution {
// 记忆的辅助数组
int[] memo;
public int integerBreak(int n) {
memo = new int[n+1];
return integerBreakCore(n);
}
private int integerBreakCore(int n) {
if (n == 2) {
return 1;
}
// 记忆数组检查（剪枝检查）
if (memo[n] != 0) return memo[n];
int res = -1;
for (int i = 1;i < n;i++) {
res = Math.max(res, Math.max(i*(n-i),i*integerBreakCore(n - i)));
}
memo[n] = res;
return memo[n];
}
}
3、动态规划
- 自下而上的递推公式
dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))
// java
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
// i= 3...n, 求出dp[i]
for (int i = 3;i <= n;i++) {
// 求最优的加数乘积
for (int j = 1;j < i;j++) {
dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
}
4、数学公式，有证明
- 将数字nn拆分为尽量多的3，可以保证乘积最大。下面简单分类讨论：
- 若$n \equiv 0(mod \ 3)n≡0(mod 3)$，即n=3k，则拆分为k个3
- 若$n \equiv 1(mod \ 3)n≡1(mod 3)$，即$n=3k+1=3(k-1)+2\times 2n=3k+1=3(k−1)+2×2$，则拆分为k-1个3，2个2
- 若$n \equiv 2(mod \ 3)n≡2(mod 3)$，即$n=3k+2n=3k+2$，则拆分为k个3，1个2
- 考虑到边界情况，当n \le 3n≤3时无法拆分，故直接讨论：
- 若
n=2，只有2=1+1，此时最大值为1 - 若
n=3，只有3=1+2，此时最大值为2 - 以上两种情形可以合并为：当$n \le 3$时，最大值为n-1
综上所述：
- 若
$$ F(n)=\left{
\begin{array}{rcl}
n - 1 & & {n \le 3}\
13^k & & {n = 3k(k \ge 2)}\
43^{k - 1} & & {n = 3k+1 (k \ge 1)}\
2*3^{k - 1} & & {n = 3k+2 (k \ge 1)}
\end{array} \right.
$$
作者：amanehayashi
链接：https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-shu-xue-fang-fa-han-wan-zheng-t/
- 代码
public class solution{
public int integerBreak(int n) {
// p有三种值：0，1，2， q>=0, r有三种值：1 4 2
int p = n%3,q = n/3, r = p + (2*p+1) % 5;
// 巧妙的计算分段函数
return n <= 3 ? n - 1:(int)(Math.pow(3, q - (p & 1)) * r);
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
