[LeetCode][Python]Integer Break

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.

Hint:

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

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

把一个数字拆成几个数字相加，这几个数的乘积要最大。

先是O(n^2)的动态规划。某个数最大的乘积，总是由比它小的数的子结果，乘以他们之间的差得来的。

但是注意也有可能是拆成两个数直接相乘的结果(从后面推断可以知道是小于6的数)。

 1 class Solution(object):
 2     def integerBreak(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         dp = [0, 1, 1]
 8         for i in range(3, n + 1):
 9             maxInt = -1 
10             for j in range(1, i):
11                 maxInt = max(maxInt, (i - j) * dp[j], (i - j) * j)
12             dp.append(maxInt)
13         return dp[n]

然后找规律，从大于7的数开始，符合规律。

为什么要以3为单位，不是4也不是5，因为：

3 * 3 * 3 * 3 > 4 * 4 * 4
3 * 3 * 3 * 3 * 3 > 5 * 5 * 5

https://leetcode.com/discuss/98249/easy-to-understand-c-with-explanation

 1 class Solution(object):
 2     def integerBreak(self, n):
 3         """
 4         :type n: int
 5         :rtype: int
 6         """
 7         dp = [0, 1, 1, 2, 4, 6, 9]
 8         if n <= 6:
 9             return dp[n]
10         return 3 * self.integerBreak(n - 3)