# 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) |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/14i.-jian-sheng-zi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.