LeetCode 343. 整数拆分（DP）
LeetCode 343. 整数拆分（DP）
Michael阿明
发布于 2020-07-13 15:46:47
发布于 2020-07-13 15:46:47
1. 题目
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。《剑指offer》同题 面试题14- I. 剪绳子
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/integer-break 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
表示获得的最大乘积
- 当 n+1 时，可以拆成
class Solution {
public:
int integerBreak(int n) {
int dp[n+1] = {0};
dp[2] = 1;
int i, j;
for(i = 3; i <= n; ++i)
{
for(j = 1; j <= i-2; ++j)
dp[i] = max(dp[i], max(j*dp[i-j], j*(i-j)));
}
return dp[n];
}
};class Solution {
public:
int cuttingRope(int n) {
int dp[n+1] = {0};
dp[2] = 1;
int i, j;
for(i = 3; i <= n; ++i)
{
for(j = 1; j < i; ++j)
dp[i] = max(dp[i], max(j,dp[j])*max(i-j, dp[i-j]));
}
return dp[n];
}
};
在这里插入图片描述
n 很大的时候，避免溢出：《剑指offer》面试题14- II. 剪绳子 II
有结论：划分成尽可能多的3，最多2个2
- 求余1，2个2
- 求余2，1个2
class Solution {
public:
int cuttingRope(int n) {
if(n <= 3)
return n-1;
//尽可能多的3, 两端最多只有2个2
int p = n/3, q = n%3;
long long sum = 1;
if(q == 1)//多分出3个，凑成4 变成2*2 > 3*1
sum *= 4, p -= 1;
if(q == 2)
sum *= 2;
for(int i = 0; i < p; i++){
sum = sum * 3 % 1000000007;
}
return sum;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录