leetcode_343

发表于   |   分类于

Integer Break

题目戳这

题意

给定一个数字n，让你将其拆分成至少两个数字相加的形式，使得拆分出来的序列乘积最大。

解法

题目提示将7到10进行拆分：

7 = 3+2+2

8 = 3+3+2

9 = 3+3+3

10 = 3+3+3+2+2

从中我们可以发现，拆分出来的序列都只包含3或者2，而且优先分配3，当且仅当n>4时我们一直分配3这个因子。

这个理论是可以被证明的，简单的来说，就是我们不需要一个>=4的因子，假如某个数字n有个因子x>=4,那么我们可以把这个因子拆分为 x = 2 + x-2,则2(x-2) = 2x-4 >= x,这个条件是当x>=4的情况下成立的。那么我们可拆分的因子就只有1，2，3。1就算了，因为它对乘积没有贡献，对于2和3来说，当它们的和相同时，比如6=2+2+2， 6=3+3,此时3\3 > 2*2*2的，所以我们要优先分配3。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 2:
            return 1
        
        if n == 3:
            return 2
        
        ssum = 1
        
        while n > 4:
            n -= 3
            ssum *= 3
        
        ssum *= n
        
        return ssum