343整数拆分


# 这道题我是用动态规划的方法来做的。
# 遍历从1 ~ n 里边所有的数差分后的最大乘积,
# 然后从中找出两个数相加等于n,判断其中的最大乘积是多少。
# 注意,这里还有一种可能,就是这个数的最大乘积,没有这个数本身大。
# 所以判断的时候用max(index2,dp[index2])

class Solution:
def integerBreak(self, n: int) -> int:
# 这里传入的数不可能是 1
dp = [0 for i in range(n + 1)]
# 这里为了简便,我把dp[1]定义成了1,其实可以写成0的。
# 因为在后边的计算中,哪怕使用到1,也是把它当做1来看
dp[1],dp[2] = 1,1
# 遍历从3 —— n的所有数。
for index1 in range(3,n + 1):
# 找出从1到index1-1的乘积,注意这里可以遍历一半
for index2 in range(1,index1 // 2 + 1):
# 动态方程,自己体会理解下
dp[index1] = max(dp[index1],max(dp[index2],index2) * max(dp[index1 - index2],index1 - index2))
return dp[n]

A =Solution()
print(A.integerBreak(10))
print(A.integerBreak(2))

作者:月为暮,发布于:2020/07/30
原文:https://www.cnblogs.com/cong12586/p/13403249.html