題目：整數(shù)拆分
給定一個正整數(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 不小于 2 且不大于 58。
思路
- 對于一個整數(shù)n可以拆分為
j和n-j尸折，那么j可能的范圍為[1,n-1] - 可以得出狀態(tài)轉移方程
dp[n] = max(j*(n-j), j*dp[n-j]) - 要得到最大的
dp[n]啰脚，需要對j可能范圍內的每一個值計算，得到最大的值。
實現(xiàn)
func integerBreak(n int) int {
dp := make([]int, n+1)
for i := 2; i <= n; i++ {
curMax := 0
for j := 1; j < i; j++ {
curMax = _max(curMax, _max(j*(i-j), j*dp[i-j]))
}
dp[i] = curMax
}
return dp[n]
}
func _max(n1, n2 int) int {
return int(math.Max(float64(n1), float64(n2)))
}
