343. Integer Break

 

Given a positive integer  n , break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that  n  is not less than 2 and not larger than 58.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

 

这道题给了我们一个正整数n,让拆分成至少两个正整数之和,使其乘积最大。最简单粗暴的方法自然是检查所有情况了,但是拆分方法那么多,怎么才能保证能拆分出所有的情况呢?感觉有点像之前那道 Coin Change,当前的拆分方法需要用到之前的拆分值,这种重现关系就很适合动态规划 Dynamic Programming 来做,我们使用一个一维数组 dp,其中 dp[i] 表示数字i拆分为至少两个正整数之和的最大乘积,数组大小为 n+1,值均初始化为1,因为正整数的乘积不会小于1。可以从3开始遍历,因为n是从2开始的,而2只能拆分为两个1,乘积还是1。i从3遍历到n,对于每个i,需要遍历所有小于i的数字,因为这些都是潜在的拆分情况,对于任意小于i的数字j,首先计算拆分为两个数字的乘积,即j乘以 i-j,然后是拆分为多个数字的情况,这里就要用到 dp[i-j] 了,这个值表示数字 i-j 任意拆分可得到的最大乘积,再乘以j就是数字i可拆分得到的乘积,取二者的较大值来更新 dp[i],最后返回 dp[n] 即可,参见代码如下:

 

解法一:

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 1);
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

 

题目提示中让用 O(n) 的时间复杂度来解题,而且告诉我们找7到 10 之间的规律,那么我们一点一点的来分析:

正整数从1开始,但是1不能拆分成两个正整数之和,所以不能当输入。

那么2只能拆成 1+1,所以乘积也为1。

数字3可以拆分成 2+1 或 1+1+1,显然第一种拆分方法乘积大为2。

数字4拆成 2+2,乘积最大,为4。

数字5拆成 3+2,乘积最大,为6。

数字6拆成 3+3,乘积最大,为9。

数字7拆为 3+4,乘积最大,为 12。

数字8拆为 3+3+2,乘积最大,为 18。

数字9拆为 3+3+3,乘积最大,为 27。

数字10拆为 3+3+4,乘积最大,为 36。

….

那么通过观察上面的规律,我们可以看出从5开始,数字都需要先拆出所有的3,一直拆到剩下一个数为2或者4,因为剩4就不用再拆了,拆成两个2和不拆没有意义,而且4不能拆出一个3剩一个1,这样会比拆成 2+2 的乘积小。这样我们就可以写代码了,先预处理n为2和3的情况,然后先将结果 res 初始化为1,然后当n大于4开始循环,结果 res 自乘3,n自减3,根据之前的分析,当跳出循环时,n只能是2或者4,再乘以 res 返回即可:

 

解法二:

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};

 

我们再来观察上面列出的 10 之前数字的规律,我们还可以发现数字7拆分结果是数字4的三倍,而7比4正好大三,数字8拆分结果是数字5的三倍,而8比5大3,后面都是这样的规律,那么我们可以把数字6之前的拆分结果都列举出来,然后之后的数通过查表都能计算出来,参见代码如下;

 

解法三:

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp{0, 0, 1, 2, 4, 6, 9};
        for (int i = 7; i <= n; ++i) {
            dp.push_back(3 * dp[i - 3]);
        }
        return dp[n];
    }
};

 

下面这种解法是热心网友留言告诉博主的,感觉很叼,故而补充上来。是解法一的一种变形写法,不再使用 while 循环了,而是直接分别算出能拆出3的个数和最后剩下的余数2或者4,然后直接相乘得到结果,参见代码如下:

 

解法四:

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        if (n == 4) return 4;
        n -= 5;
        return (int)pow(3, (n / 3 + 1)) * (n % 3 + 2);
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/343

 

参考资料:

https://leetcode.com/problems/integer-break/

https://leetcode.com/problems/integer-break/discuss/80694/Java-DP-solution

https://leetcode.com/problems/integer-break/discuss/80785/O(log(n))-Time-solution-with-explanation

https://leetcode.com/problems/integer-break/discuss/80720/Easy-to-understand-C%2B%2B-with-explanation

https://leetcode.com/problems/integer-break/discuss/80689/A-simple-explanation-of-the-math-part-and-a-O(n)-solution

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation