# 這道題我是用動態規劃的方法來做的，
# 遍歷從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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/73433.html
標籤：Python
上一篇：Python變數和資料型別簡介