已认证网站服务费怎么做/外链购买
题目描述:
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例:
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。
思路:
思路1:找规律
2 : 1 + 1
3: 1 + 2
4: 2 + 2
5 : 3 + 2
6: 3 + 3
7: 2 + 2 + 3
8: 2 + 3 +3
...我们看出每当我们加1时候,如果使累加项出现4,我们就把它拆成2+2,这样求出乘积最大.
时间复杂度:
思路2:动态规划
动态转移方程:dp[i] = max(dp[i],max(dp[j],j)*max(dp[i-j],i-j))
时间复杂度:
代码:
思路1:
def integerBreak(self, n):if n == 2: return 1if n == 3: return 2lookup = {4, 3, 2}res = 1while n:while n - 4 > 0:n -= 3res *= 3if n in lookup:res *= nn -= nreturn res思路2:
def integerBreak(self, n):dp = [1] * (n + 1)for i in range(2, n + 1):for j in range(1, i):dp[i] = max(dp[i], max(j, dp[j]) * max(dp[i - j], i - j))return dp[n]