leetcode Integer Break

leetcode 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.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

题目地址：leetcode Integer Break

题意:给定整数n（n>=2），把它分解为若干个整数的和，且这些整数的乘积最大。

思路：

一觉起来发现李大牛出题了。。

这种题肯定是DP嘛

设dp[i]为最大的乘积值，水水的O(n^2)代码如下：

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [1] * (n + 1)
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                if i + j > n: 
                    break
                dp[i + j] = max(dp[i + j], max(dp[i], i) * max(dp[j], j))
        return dp[n]

但是hint说可以O(n)!

在n >3的情况下，我们处理一个数拆分成2，要么拆分成3，（4的话相当于2个2 ，拆成1的话乘积太小了），所以就可以这样啦：

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        for i in range(4, n + 1):
            dp[i] = max(dp[i - 3] * 3, dp[i - 2] * 2)
        return dp[n]

然而还可以继续优化：

可以说，拆成3的比拆成2的乘积大。比如6的时候 \(2*2*2 < 3*3\)

我们希望能尽可能的拆成3，然后才是2.

所以，如果

n % 3 == 0: 那么全部拆成3
n % 3 == 1: 2个2剩下的为3 \(4*3^{(x-1)} > 1*3^x\)
n % 3 == 2: 1个2剩下的为3

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 3 :return n-1
        mod = n % 3
        if mod == 0: return pow(3, n / 3)
        if mod == 1: return 4 * pow(3, (n - 4) / 3)
        return 2 * pow(3, n / 3)

Python 3版本

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        mod = n % 3
        if mod == 0: 
            return 3 ** (n // 3)
        elif mod == 1: 
            return 4 * 3 ** (n // 3 - 1)
        else:
            return 2 * 3 ** (n // 3)

本题是leetcode 343 Integer Break 题解，

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/