Integer Break

发表于 更新于 本文字数： 210 阅读时长 ≈ 1 分钟

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 and not larger than 58.

思路: 最值问题,求导.
假设一个数N分成了N/x份,每份都是x,则有
$$
y=x^{N/x},\
\ln y=(N/x)\ln x,\
\frac{1}{y}*y^{‘}=\frac{n}{x^2}(1-\ln x),
$$
另y’=0,则有lnx=1,x=e.
题中规定x只能是正整数,e约为2.718,则取离e较近的数3,此时y较大.
于是有递推式: dp(i)=3dp(i-3) (i>4 ),i<=4时,dp[i]=[1,1,1,2,4].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        bottom to up dp.
        """
        res=[1,1,1,2,4]
        if n<=4:return res[n]
        else:
            ans=1
            while n>4:
                ans*=3
                n-=3
            ans*=n
        return ans