# 14.II.剪绳子

## 一、 题目

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

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

示例 2:

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

提示：

2 <= n <= 1000

注意：本题与[主站 343 题](https://leetcode-cn.com/problems/integer-break/)相同

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

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

## 二、 常规思路与问题

咋一看，和[14-I.剪绳子](/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/14i.-jian-sheng-zi.md)没什么区别嘛～ 不就是结果要取模嘛～

### 2.1 一般思路

***那你就上当了***

我们用动态规划的解法来试试：

```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] % 1_000_000_007
}
```

试试两个测试用例：

```
10 - 36
2 - 1
```

***很正常没问题嘛～🤷‍♂️***

### 2.2 试试120

![120](/files/-MfYpocx-I9xTENkfG-m)

***居然出错了？***

### 2.3 数据长度问题

请注意本题的数据范围 `2 <= n <= 1000` 和第一题的 `2 <= n <= 58`，差别很大。

上面报错就是因为数据超出了范围了。

> 那你可能会想到，那我换 `Int64` ？我换 `long` ？

然鹅并不行

> 那我每次纯数据都取一下模？

更不行，中间数据都变了，结果当然更错

#### 我们用 `Decimal` 来接收看看`120`时到底是多大：

![12157665459056928801](/files/-MfYpocz_vJRQSOFz80i)

`120` 时就已经 `20位` 了，更何况本题的范围最大`1000`。

> 我们就不要再数据类型的选择上进行纠结了

### 2.4 `Decimal` 解法

这里将元素使用 `Decimal` 进行承载

```swift
let base = NSDecimalNumber(decimal: Decimal(1_000_000_007))

func cuttingRope(_ n: Int) -> Int {
    if n < 4 {
        return n - 1
    }

    var dp = [Decimal](repeating: 1, count: n + 1)
    for i in 3...n {
        for j in 2..<i {
            dp[i] = max(dp[i], max(Decimal(j) * Decimal(i - j), Decimal(j) * dp[i - j]))
        }
    }

    let handler = NSDecimalNumberHandler(roundingMode: .down, scale: 0, raiseOnExactness: false, raiseOnOverflow: false, raiseOnUnderflow: false, raiseOnDivideByZero: false)

    let result = NSDecimalNumber(decimal: dp[n])
    let baseCount = result.dividing(by: base).rounding(accordingToBehavior: handler)

    let tp = result.subtracting(base.multiplying(by: baseCount))

    return Int(truncating: tp)
}
```

![Decimal](/files/-MfYpod-1kfgPJ8Yot2o)

![Decimal](/files/-MfYpod0GqM99r2meh8Z)

结果到 255 的时候还是错了，还是丢失了精度。毕竟 `NSDecimalNumber` 也是有范围的

![Decimal](/files/-MfYpod1ySTsG3YGsvDs)

> 感觉想继续用动态规划不太现实了

### 2.5 补充 Java 的 BigInteger 可以动态规划

```swift
import java.math.BigInteger;
class Solution {
    public int cuttingRope(int n) {
        BigInteger[] dp = new BigInteger[n + 1];
         Arrays.fill(dp, BigInteger.valueOf(1));
        // dp[1] = BigInteger.valueOf(1);
        for(int i = 3; i < n + 1; i++){
            for(int j = 1; j < i; j++){
                dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
            }
        }
        return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
    }
}
```

链接：[作者：ollieq](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/jian-dan-li-jie-dong-tai-gui-hua-xun-hua-4g3o/)

> 这里就不再纠结数据类型了

## 三、 贪心-循环求余

> 尽可能多的切成长度为3的，乘积最大

### 3.1 解法

```swift
func cuttingRope(_ n: Int) -> Int {
    if n < 4 {
        return n - 1
    }
    var res = 1
    var n = n
    while n > 4 {
        res = res * 3 % 1_000_000_007
        n -= 3
    }
    return res * n % 1_000_000_007
}
```

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

![真的是快](/files/-MfYpod5T-w3MGsUrifO)

***真快***

### 3.2 循环求余

详细可以移步[这个题解](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/)

![循环求余](/files/-MfYpod6J61AESMlJPIS)

## 四、贪心-快速幂

核心是通过 `快速幂` 算法及模运算规律，控制数据范围。详细了解可以移步[快速幂](/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/03.-kuai-su-mi.md)

> [LeetCode](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/tan-xin-kuai-su-mi-by-happy-austin9mq-6bxz/)

### 4.1 解法

```swift
func cuttingRope(_ n: Int) -> Int {
    if n < 4 {
        return n - 1
    }
    let a = n / 3, b = n % 3

    if b == 0 {
        return modPow(3, a) % 1_000_000_007
    }
    else if b == 1 {
        return modPow(3, a - 1) * 4 % 1_000_000_007
    }
    else {
        return modPow(3, a) * 2 % 1_000_000_007
    }
}

func modPow(_ x: Int, _ n: Int) -> Int {
    var res = 1
    var x = x
    var n = n

    while n > 0 {
        if n & 1 == 1 {
            res *= x
            res %= 1_000_000_007 // 限制了数据范围
        }
        x *= x
        x %= 1_000_000_007 // 限制了数据范围
        n >>= 1
    }

    return res
}
```

![快速幂](/files/-MfbcORoNu_ZlH3pUwiZ)


---

# 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/14ii.-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.