# 面试题14
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0],k\[1]...k\[m] 。请问 k\[0]*k\[1]*...\*k\[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
```
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
```
## 提示：
* 2 <= n <= 1000
## 注意：本题与主站 343 题相同：
## Solutions
1. **dynamic programing O(n)**
```cpp
class Solution {
public:
int cuttingRope(int n) {
vector dp(n + 1);
dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
return dp[n];
}
};
```
1. **math**
```cpp
class Solution {
public:
int cuttingRope(int n) {
if (n <= 3) return n - 1;
else if (n % 3 == 1)
return 4 * pow(3, (n - 4) / 3);
else if (n % 3 == 2)
return 2 * pow(3, (n - 2) / 3);
else return pow(3, n / 3);
}
};
```
or
```cpp
class Solution {
public:
int cuttingRope(int n) {
if (n <= 3) return n - 1;
long res = 1;
while (n > 4) {
res = res * 3 % 1000000007;;
n -= 3;
}
return res * n % 1000000007;
}
};
```
---
# 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://zhongquan789.gitbook.io/leetcode/lcof/mian-shi-ti-14.md?ask=
```
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.