《剑指offer刷题笔记》13、剪绳子【c++详细题解】

朱雀 2021-07-24 22:40 378阅读 0赞

### 题目 ###

给你一根长度为  n n n绳子，请把绳子剪成 m m m段（ m m m、 n n n 都是整数， 2 ≤ n ≤ 58 2≤n≤58 2≤n≤58 并且  m ≥ 2 m≥2 m≥2）。

每段的绳子的长度记为 k \[ 1 \] 、 k \[ 2 \] 、 … … 、 k \[ m \] k\[1\]、k\[2\]、……、k\[m\] k\[1\]、k\[2\]、……、k\[m\]。

k \[ 1 \] k \[ 2 \] … k \[ m \] k\[1\]k\[2\]…k\[m\] k\[1\]k\[2\]…k\[m\]可能的最大乘积是多少？

例如当绳子的长度是  8 8 8时，我们把它剪成长度分别为 2 2 2、 3 3 3、 3 3 3、 的三段，此时得到最大的乘积 18 18 18。

**样例**

输入：8
    
    输出：18

### **思路** ###

**(数学)**  O ( n ) O(n) O(n)  
这道题目是数学中一个很经典的问题。  
下面我们给出证明：

首先把一个正整数  N N N 拆分成若干正整数只有有限种拆法，所以存在最大乘积。  
假设  N = n 1 + n 2 + … + n k N=n1+n2+…+nk N=n1\+n2\+…\+nk，并且  n 1 × n 2 × … × n k n1×n2×…×nk n1×n2×…×nk是最大乘积。

1.  显然1不会出现在其中；
2.  如果对于某个 i i i有 n i ≥ 5 ni≥5 ni≥5，那么把  n i ni ni拆分成  3 + ( n i − 3 ) 3+(ni−3) 3\+(ni−3)，我们有  3 ( n i − 3 ) = 3 n i − 9 > n i 3(ni−3)=3ni−9>ni 3(ni−3)=3ni−9>ni；
3.  如果  n i = 4 ni=4 ni=4，拆成  2 + 2 2+2 2\+2乘积不变，所以不妨假设没有4；
4.  如果有三个以上的2，那么  3 × 3 > 2 × 2 × 2 3×3>2×2×2 3×3>2×2×2，所以替换成3乘积更大；
5.  综上，选用尽量多的 3 3 3，直到剩下 2 2 2或者 4 4 4时，用 2 2 2。

**时间复杂度分析**：

当  n n n比较大时， n n n 会被拆分成  ⌈ n / 3 ⌉ ⌈n/3⌉ ⌈n/3⌉ 个数，我们需要计算这么多次减法和乘法，所以时间复杂度是 O ( n ) O(n) O(n)。

### **代码** ###

class Solution { 
    public:
        int maxProductAfterCutting(int n) { 
            if(n <= 3 ) return 1*(n-1);  //边界问题,至少要剪成两段
            int res = 1;
            if(n % 3 == 1)  res = 4 , n -= 4;  //将4剪去
            else if(n % 3 == 2)  res = 2, n -= 2;
            while(n)
            { 
                res *= 3;
                n -= 3;
            }
            return res;
        }
    };

[AcWing y总题解][AcWing y]

[AcWing y]: https://www.acwing.com/solution/content/731/