mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 00:25:22 +08:00
21 lines
331 B
Go
21 lines
331 B
Go
package leetcode
|
|
|
|
func integerBreak(n int) int {
|
|
dp := make([]int, n+1)
|
|
dp[0], dp[1] = 1, 1
|
|
for i := 1; i <= n; i++ {
|
|
for j := 1; j < i; j++ {
|
|
// dp[i] = max(dp[i], j * (i - j), j*dp[i-j])
|
|
dp[i] = max(dp[i], j*max(dp[i-j], i-j))
|
|
}
|
|
}
|
|
return dp[n]
|
|
}
|
|
|
|
func max(a int, b int) int {
|
|
if a > b {
|
|
return a
|
|
}
|
|
return b
|
|
}
|