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

题目给你一根长度为 nnn绳子，请把绳子剪成mmm段（mmm、nnn 都是整数，2≤n≤582≤n≤582≤n≤58 并且 m≥2m≥2m≥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]可能的最大乘积是多少？例如当绳子的长度是 888时，

林小鹿@

292人浏览 · 2021-04-06 19:37:16

林小鹿@ · 2021-04-06 19:37:16 发布

题目

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

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

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

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

样例

输入：8

输出：18

思路

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

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

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

时间复杂度分析：

当 $n$ 比较大时， $n$ 会被拆分成 $⌈ n / 3 ⌉$ 个数，我们需要计算这么多次减法和乘法，所以时间复杂度是 $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;
    }
};