---

題目

給你一根長度為 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

來源：力扣（LeetCode）

---

數論

數學的魅力被展現的淋漓盡致~

思路

1. 除非不得已的情況，否則不要剪成長度為1的段（1乘n等于n，對于最大乘積沒有提升）。
2. 任何大于1的數都可由2和3相加組成（根據奇偶證明）。
3. 因為2*2=1*4，2*3>1*5, 所以將數字拆成2和3，能得到的積最大。（4和5還是拆分成2、3更有利）
4. 因為2*2*2<3*3, 所以3越多積越大

---

代碼

class Solution {
public:int cuttingRope(int n) {return n <= 3? n - 1 : pow(3, n / 3) * 4 / (4 - n % 3);}
};

復雜度分析

時間復雜度：O(log(n/3))
空間復雜度：O(1)

---

動規一

這個版本比較好理解。

思路

1. 每段都應該為3或者2（證明段應該為2或3不再贅述）。
2. 將n=2和n=3時最大乘積作為不具有規律的特殊值直接返回（因為n<=3時無法切分成3，不具有第一點所說的規律）。
3. 動態規劃數組dp中 下標為n 的位置保存著 長度為n的繩子的最大乘積（n=2，3時不再此列，已做特殊處理）。
4. dp數組的長度：由于定義 dp[i] 為繩長度為 i 時的結果，因此 dp[n] 為最后一項，所以數組的總長度為 n + 1 。
5. dp下標為1，2，3中保存的就是1，2，3，其含義是 當n>3時，3已經不用在切分了， 切成1，2的話最大乘積也就是2，不切的話得到3，比切了得到的2更大（dp[2]同理）。

---

代碼

class Solution {
public:int cuttingRope(int n) {if(3 >= n){return n-1;}vector<int> dp(n+1，0);dp[1] = 1;dp[2] = 2;dp[3] = 3;for(int i = 4; i <= n; i++){ // n > 3的處理// j<=i/2是因為1*3和3*1是一樣的，沒必要計算在內，只要計算到1*3和2*2就好了for(int j = 2; j <= i/2; j++){// 剪一段長度為1的繩子對乘積的提升沒有作用// 因此從2開始剪dp[i] = max(dp[i], dp[j] * dp[i-j]);}}return dp[n];}
};

動規二

有一點抽象，但是不做特殊值的處理，屬于力求包含所有規律的“正規”動規。

思路

1. 將 n=2 的值作為歷史值，開始求規律。
2. max(dp[i-j], i-j) 對于這一步可能是最難理解的，其實這只是為了處理 n=3 的特殊情況，邏輯思想是： 減去 j 后，剩余部分可以剪也可以不剪。如果不剪，則得到的長度乘積為 j * (i - j) ；如果剪，得到的長度為 j * dp[i - j] 。兩者取最大值。

為什么說這只是為了處理 n=3 的特殊情況呢？
其實在數論方法中我們已經提到過了—— 因為2*2=1*4，2*3>1*5, 所以將數字拆成2和3，能得到的積最大。（4和5還是拆分成2、3更有利），也就是僅對于 2（和3） ，有 dp[2] （dp[3]）小于 2(3)，在 n>3 時，max(dp[i-j], i-j) 的結果是恒定的—— dp[n] > n。

---

代碼

class Solution {
public:int cuttingRope(int n) {if(n == 2){return 1;}vector<int> dp(n+1);dp[2] = 1;for (int i=3; i<=n; ++i){ // n >= 3for (int j=1; j<=i/2; ++j){// j 減去的長度dp[i] = max(max(dp[i-j], i-j) * j, dp[i]);}}return dp[n];}
};

對最終結果取模1e9+7

思路

動規是用不了了，因為：

• 計算結果可能會超出int/long范圍
• 取余之后max函數就不能用來比大小了（所有大于1e9+7的數取模后就小于1e9+7了，也就是 n=120 以后最大乘積的值都是固定的）

因此應該用貪心的思想。

代碼

class Solution {
public:int cuttingRope(int n) {if(n<=3){return n - 1;}int flag = 1000000007;long sum = 1;while(n > 4){sum = (sum * 3) % flag;n -= 3;}return (sum * n) % flag;}
};