343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

image.png
image.png

  1. //从上到下，   时间On^2，空间On
  2. func integerBreak(n int) int {
  3.     dp := make([]int, n+1)
  4.     for i := 2; i <= n; i++ {
  5.         res := 0
  7.         for j := 1; j <=i; j++ {
  8.             res = max(res, max(j * (i-j), j * dp[i-j]))        //三种情况：不拆，拆到底，继续拆！
  9.         }
  10.         dp[i] = res        //其中dp[i] 表示将正整数i 拆分之后，这些正数の最大乘积
  11.     }
  12.     return dp[n]
  13. }
  15. func max(x, y int) int {
  16.     if x > y {
  17.         return x
  18.     }
  19.     return y
  20. }
//从上到下，+记忆化存储  时空都是On
func integerBreak(n int) int {
    if n <= 3 {
        return n-1
    }

    dp := make([]int, n + 1)
    dp[2] = 1

    // i 分成了 j 和 i-j 之后不再分
    // i 分成了 j 之后，继续分，但是 i-j 继续分的最大值已经计算出来了，就是 dp[i-j]
    for i := 3; i <= n; i++ {
        dp[i] = max(max(2 * (i - 2), 2 * dp[i - 2]), max(3 * (i - 3), 3 * dp[i - 3]))
    }
    return dp[n]
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}