剑指 Offer 14- I. 剪绳子

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

  1. //背包问题：二维dp，时间O^2，空间on
  2. func cuttingRope(n int) int {
  3.     dp := make([]int, n+1)              //其中dp[i] 表示将正整数i 拆分之后，这些正数の最大乘积
  5.     for i := 2; i <= n; i++ {
  6.         dp[0], dp[1] = 0, 1
  7.         dp[2] = 1
  9.         for j := 1; j <= i; j++ {
  10.             dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])) //三种情况：不拆，拆到底，继续拆！
  11.         }
  12.     }
  13.     return dp[n]
  14. }
  16. func max(x, y int) int {
  17.     if x > y {
  18.         return x
  19.     }
  20.     return y
  21. }