0343._Integer_Break.md

343. Integer Break

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

记忆化搜索，beats 97.64%

Top down

这里要注意我们可以将n分割为

• i和n-i恰好两部分
• 也可以将n分割为i和self.integerBreak(n-i)（即更多部分）

class Solution(object):
    cache = {
        1: 1
    }
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n in self.cache:
            return self.cache[n]
        self.cache[n] = -1
        for i in range(1, n):
            self.cache[n] = max(self.cache[n], i * (n-i), i * self.integerBreak(n-i))
        return self.cache[n] 

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

典型DP，Bottom up, beats 62.57%

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        cache = [1] * (n+1)
        for i in range(2, n+1):
            for j in range(1, i):
                cache[i] = max(cache[i], j * (i-j), j * cache[i-j])
        return cache[-1] 

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******

参考Why factor 2 or 3? The math behind this problem.

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 2: # 1 * 1
            return 1
        if n == 3: # 1 * 2
            return 2
        if n == 4: # 2 * 2
            return 4
        res = 1
        while n > 4:
            res *= 3
            n -= 3
        return res * n