LeetCode Integer Break

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.


给定一个数n,要求把其拆分成至少两个数的和,使得他们的乘积最大。 数学题,没啥思路,参考网上题解。 把0~10的结果先列出来找找规律:

  • 0:0
  • 1:0
  • 2:1=1*1
  • 3:2=2*1
  • 4:4=2*2
  • 5:6=3*2
  • 6:9=3*3
  • 7:12=3*4
  • 8:18=3*3*2
  • 9:27=3*3*3
  • 10:36=3*3*4

可以发现,n从5开始,都至少分解出来一个3,可以推断的是,当n=11时,在10的基础上,把最后一个4改成5,然后5又可以分解成3*2,所以11=3+3+3+2使得乘积最大。 4只能分解出2+2,1+3的乘积是3小于2*2;5可以分解出3+2,所以也有3。也就是说,当n大于4时,不断分解出3来,直到剩余的数小于4为止。所以有如下代码:

class Solution {
public:
    int integerBreak(int n)
    {
        if (n <= 3)
            return n – 1;
        int ans = 1;
        while (n > 4) {
            ans *= 3;
            n -= 3;
        }
        return ans * n;
    }
};

本代码提交AC,用时0MS。
再次观察上述规律,n=10的结果是n=7=10-3的结果乘以3;n=9的结果也是n=6=9-3的结果乘以3。可以推断,n的结果是(n-3)的结果乘以3。所以先列出前几个结果,后面的结果通过其前3的结果乘以3推导得到。代码如下:

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(dp[i – 3] * 3);
        return dp[n];
    }
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *