# 14.I.剪绳子

## 一、 题目

给你一根长度为 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：

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

示例 2:

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

提示：

2 <= n <= 58

注意：本题与主站 343 题相同：<https://leetcode-cn.com/problems/integer-break/>

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/jian-sheng-zi-lcof)

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 二、 动态规划

动态规划是面试中的热门话题。

### 2.1 什么样的场景适合动态规划呢？

* 如果题目是：
  * 求一个问题的最优解（通常是`最大值`或者`最小值`）
  * 而且改问题能够分解为若干个子问题
  * 并且字问题之间还有重叠的更小的子问题
* 就可以考虑使用动态规划来解决这个问题

### 2.2 本题是否适合动态规划？

* 我们把长度为n的绳子剪成若干段后得到的乘积的最大值定义为函数`f(n)`。
* 假设我们把第一刀剪在了长度为`i（0 < i < n）`的位置，于是把绳子剪成了长度为`i`和`n-i`的两段。
* 我们想要得到整个问题的最优解`f(n)`那么要同样用最优化的方法把长度为`i`和`n-i`的两段分别剪成若干段，使得各自剪出的每段绳子的乘积最大。
* 也就是说整体问题的最优解是依赖各个子问题的最优解。

### 2.3 动态规划的过程

* 由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以：
  * 从下往上的顺序先计算小问题的最优解并存储下来
  * 再以此为基础求取大问题的最优解
* 这种从上往下分析问题，从下往上解决问题也是动态规划的一大特征。

### 2.4 应用在本题中

在应用动态规划的时候，我们每一步都可能面临若干个选择。

本题中：

* 第一刀有n-1种选择。我们可以剪再 1,2...n-1 的任意位置。
* 由于我们事先不知道那个位置是最优解，只好把所有可能的额都尝试一遍，然后比较出最优解。
* 用数学表示就是
  * `f(n) = max(f(i), f(n-i))`
  * `0 < i < n`

### 代码

```swift
func cuttingRope(_ n: Int) -> Int {
    if n < 4 {
        return n - 1
    }
    var dp = [Int](repeating: 1, count: n + 1)
    for i in 3...n {
        for j in 2..<i {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        }
    }
    return dp[n]
}
```

|  时间复杂度 | 空间复杂度 |
| :----: | :---: |
| O(n^2) |  O(n) |

## 三、 贪婪算法

贪婪算法和动态规划不一样。当我们应用贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。

至于为什么这样的贪婪选择能够得到最优解。这就需要使用数学方式来证明了。

### 3.1 应用再本题中

* 如果绳子长度大于5，则每次都剪出一段长度为3的绳子。
* 如果剩下的长度仍然大于5，则接着剪出一段长度为3的绳子。
* 循环
* 直到剩下的绳子长度小于5。
  * 当绳子长度为4时，剪成 2x2=4
  * 当绳子长度为3时，剪成 1x2=2
  * 当绳子长度为2时，剪成 1x1=1
    * 其实不剪最大，但要求至少剪一刀那就剪呗

`剪出一段长度为3的绳子`就是我们在每一步做出的贪婪选择。

### 3.2 证明上面思路的正确性

* 当n>=5时
  * 2(n-2)>n && 3(n-3)>n
  * 也就是说当绳子的长度大于或等于5时，我们可以把它剪成3或2的绳子段
* 另外当n>=5
  * 3(n-3)>=2(n-2)
  * 因此我们应该尽可能多的剪长度为3的绳子

> 上面时原书中的解释，更详细专业的证明[Krahets](https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/)

### 代码

```swift
func cuttingRope(_ n: Int) -> Int {
    if n < 2 {
        return 0
    }
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }

    // 3长度的最大段数
    var threeCount = n / 3

    // 当绳子剩下4的时候 不能再剪3长度，更优的方式是剪成长度为2的，因为 2x2 > 3x1
    if n - threeCount * 3 == 1 {
        threeCount -= 1
    }
    let twoCount = (n - threeCount * 3) / 2

    return Int(truncating: NSDecimalNumber(decimal: pow(3, threeCount))) * Int(truncating: NSDecimalNumber(decimal: pow(2, twoCount)))
}
```

| 时间复杂度 | 空间复杂度 |
| :---: | :---: |
|  O(1) |  O(1) |