剪绳子

## 1 题目

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

**示例 1：**

```txt
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
```

**示例 2:**

```txt
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
```

**提示：**

* 2 <= n <= 58

> 相似题目：
>
> 1. [剑指 Offer 14- II. 剪绳子 II](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof)。

## 2 问题分析

1. 首先**定义函数 $f(n)$ 为把长度为 $n$ 的绳子剪成若干段后各段长度乘积的最大值**。
2. **在剪第一刀的时候**，**我们有 $n - 1$ 种可能的选择**，**也就是剪出来的第一段绳子的可能长度分别为 $ 1, 2, ..., n - 1$**，因此 $f(n) = max(f(i) \times f(n - i))$，其中 $ 0 < i < n$。
3. **这是一个从上至下的递归公式**，**由于递归会有很多重复的子问题**，**从而有大量不必要的重复计算**，**一个更好的方法是按照从下而上的顺序计算**，**也就是说我们先得到 $f(2)$**、**$f(3)$**，**再得到 $f(4)$**、**$f(5)$**，**直到得到 $f(n)$**。
4. **当绳子长度为 2 时**，**只可能剪成长度都为 1 的两段**，**因此 $f(2)$ 等于 1**，**当绳子的长度为 3 时**，**可能把绳子剪成长度分别为 1 和 2 的两段或者长度都为 1 的三段**，**由于 $ 1 \times 2 > 1 \times 1 \times 1$**，**因此 $f(3) = 2$**。

## 3 参考代码

```java
/**
 * 剑指 Offer 14- I. 剪绳子
 * @param n 绳子长度
 * @return  剪成 m 段后所有段长的最大乘积
 */
public int cuttingRope(int n) {
    //  dp 数组，其中 dp[i] 表示长度为 i 的绳子剪成 m 段后所有段长的最大乘积
    int[] dp = new int[n + 1];

if (n == 2) {return 1;}
    if (n == 3) {return 2;}

dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

for (int i = 4; i <= n; i++) {
        for (int j = 1; j <= i / 2; j++) {
            //  转移方程
            dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
        }
    }

//  返回最后结果
    return dp[n];
}
```

## 参考文献

1. [剑指 Offer 14- I. 剪绳子](https://leetcode-cn.com/problems/jian-sheng-zi-lcof)。
2. [无需复杂数学！二元基本不等式分析动态规划、贪心算法](https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/jian-zhi-offermian-shi-ti-14suan-fa-zhon-6bxx)。
3. [剑指 Offer-14：剪绳子](https://blog.csdn.net/Koala_Tree/article/details/78932316)。
4. [剑指 Offer 14- II. 剪绳子 II](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof)。