描述

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]k[2]...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围： 2≤n≤60
进阶：空间复杂度 O(1)，时间复杂度 O(n)

输入描述：输入一个数n，意义见题面。

示例

// 输入：
8
// 返回值：
18
// 说明：
8 = 2 +3 +3 , 2*3*3=18

// 输入：
2
// 返回值：
1
// 说明：
m>1，所以切成两段长度是1的绳子

代码实现

/**
 * 动态规划
 *
 * @param n int 整型
 * @return int 整型
 */
func cutRope(n int) int {
    if n <= 3 {
        return n - 1
    }

    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3
    dp[4] = 4
    for i := 5; i <= n; i++ {
        for j := 1; j < i; j++ {
            if dp[i] > j*dp[i-j] {
                dp[i] = dp[i]
            } else {
                dp[i] = j * dp[i-j]
            }
        }
    }
    return dp[n]
}