LeetCode343-整数拆分

昨天晚上写作业时

腾讯的一条笔试通知邮件

着实让我有点吃惊

我三月份就投了鹅厂

身边的朋友早就面试了

自己的简历杳无音讯

本早就放弃了

却没想还能最后有次机会

害，要好好珍惜了。

题目描述：

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

思路解析：

这中类型的题目拿过来看都不看直接就是动态规划解决了，因为题目给的是拆分为至少两个正整数的和，也就是可能是2个，是3个，是4个等。没有告诉你拆分成几个，你直接硬着头皮做实完全没有思路的。我们只能是分别记录0-n之间每个值对应的乘积最大值，然后找到动态回归方程，利用之前的规律值快速求解。下面举几个例子示范。此时我们定义标记矩阵为dp[i](i=0,1,2...)，其中i对应给定的输入数字n

输入: 3
输出: 2
解释: 2 = max(dp[1]*dp[2], 1*dp[2], dp[1]*2, 1*2, dp[3])

因为dp[2]=1,dp[1]=1（dp[1]正常逻辑来讲没有意义，这儿为了规范还是加上了）,最后统计所有值，发现1*2能得到最大值，所以dp[3]=2

输入: 4
输出: 4
解释: 4 = max(dp[1]*dp[3], dp[2]*dp[2], 1*dp[3], dp[1]*3, 1*3, 2*dp[2], dp[2]*2, 2*2, dp[4])

最后发现是2*2=4得到最大值。

由这两个例子，我们总结出的动态转移方程为：

其中i=1,2,...n-1.

代码如下：

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


if __name__ == "__main__":
    n = 10
    print(Solution().integerBreak(n))

执行效率中等吧，在50%左右。