題目

給你一根長度為?n?的繩子，請把繩子剪成整數(shù)長度的?m?段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長度記為?k[0],k[1]...k[m-1]?。請問?k[0]*k[1]*...*k[m-1]?可能的最大乘積是多少？例如，當(dāng)繩子的長度是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

解題思路

1.題目要求我們將繩子剪切為乘積最大的 m 段，這其中蘊(yùn)含著一個數(shù)學(xué)問題，就是當(dāng)我們盡可能將繩子以長度?3等分為多段時，乘積最大。這個推論大家可以自己去證明一下。

2.有了這個推論，這個問題就輕而易舉了，

①切分規(guī)則：
最優(yōu)： 3 。把繩子盡可能切為多個長度為 3 的片段，留下的最后一段繩子的長度可能為 0,1,2 三種情況。
次優(yōu)： 2。若最后一段繩子長度為 2 ；則保留，不再拆為 1+1 。
最差： 1。若最后一段繩子長度為 1 ；則應(yīng)把一份 3+1 替換為 2+2，因?yàn)?2×2>3×1?
②算法流程：

• 當(dāng) n≤3 時，按照規(guī)則應(yīng)不切分，但由于題目要求必須剪成 m>1 段，因此必須剪出一段長度為 1 的繩子，即返回 n?1 。
• 當(dāng) n>3 時，求 n?除以 3?的 整數(shù)部分 res?和 余數(shù)部分 mod （即 n=3res+ mod?=），并分為以下三種情況：

? ? ? ?①當(dāng) b=0 時，直接返回 3^a；

? ? ? ?②當(dāng) b=1 時，要將一個 1+3 轉(zhuǎn)換為 2+2，因此返回 3^{a-1} *4

? ? ? ?③當(dāng) b=2 時，返回 3^a*2?

代碼實(shí)現(xiàn)

class Solution {public int cuttingRope(int n) {if(n <= 2){return 1;}if(n == 3){return 2;}int res = n / 3;int mod = n % 3;if(mod == 0){return pow(3,res);}else if(mod == 1){return pow(3,res - 1) * 4;}else {return pow(3,res) * 2;}}int pow(int i, int k){int sum = 1;for(i = 1; i <= k; i++){sum = sum * 3;}return sum;}}

測試結(jié)果

?