題目鏈接
難度：中等 ??????類型： 數(shù)學(xué)提陶、動態(tài)規(guī)劃
給定一個正整數(shù) n咕缎，將其拆分為至少兩個正整數(shù)的和像寒，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積喂江。
示例1
輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。
示例2
輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36旁振。
解題思路
n<=3時获询，返回n-1
當n>=4時，最大乘積一定是由k個2和m個3組成的
dp[i]表示i拆分后的最大乘積拐袜，其中i>=4吉嚣， 為了dp[4],dp[5],dp[6]能正常計算，需要初始化dp[0]=dp[1]=0,dp[2]=2,dp[3]=3
狀態(tài)轉(zhuǎn)移矩陣為dp[i] = max(dp[i-2]2 , dp[i-3]3)
代碼實現(xiàn)
class Solution:
def integerBreak(self, n: int) -> int:
if n<=3:
return n-1
dp = [0] * (n+1)
dp[1:4] = [1, 2, 3]
for i in range(4, n+1):
dp[i] = max(2*dp[i-2], 3*dp[i-3])
return dp[n]
