一道快手的算法面试题，没想到对数学要求还蛮高的！

た入场券 2023-02-20 10:41 4阅读 0赞

点击上方“**图解面试算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

大家好，我是景禹。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题14.I 剪绳子。根据统计，近期出现在快手的算法面试环节，属于中等难度，需要一定的数学功底。

题目链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

## 题目描述 ##

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且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

## 题目解析 ##

### 一、数学推导法 ###

设绳子长度为，总共拆分为段，每一段的长度均为，请问 每一段的长度为多少时，乘积最大呢？

设绳子的长度为，且切分为段，则得到的乘积为（这里我们假设每一段的长度均为，则这道题目就转化为一个求函数关于的一个最大值问题，稍微翻一下大学课本里的高等数学书中求导相关的内容，接着看；

对函数两边同时取对数：

上式两边对求导，注意，得：

![format_png 2][]

于是

令，则，则;

即，当每一段绳子的长度取时，乘积取得最大值，但是每一段绳子的长度只能取整数，到底是取 2 好 还是取 3 好呢？

当时，等分的话，可以是，也可以是，乘积则分别对应和，显然，所以当然是取 3 好了。

也就是说对于长度为的绳子，我们尽可能以每一段为 3 进行分割，得到的乘积最大。

当绳子的长度时，也就两种情况（因为题目中绳子的长度要求是：

1.  ，只能拆为，乘积为 1 ；
2.  ，只能拆为，乘积为 2 ；

![format_png 3][]

当绳子的长度时，我们就可以直接用对 3 进行求余运算，设商数为，余数为，即，其中余数又分为三种情况进行处理：

1.  余数，此时直接返回即为最大的乘积，比如是，最大乘积为；时，最大乘积为；整除的情况都是如此。
2.  余数，此时直接返回是不对的，为什么呢？因为
    
    所以当时，而是返回. 比如，最大乘积为；当，最大乘积为;
3.  余数， 此时直接返回即可。比如，最大乘积为；当，最大乘积为。

![format_png 4][]

#### 实现代码 ####

class Solution {
        public int cuttingRope(int n) {
            if(n <= 3){
                return n-1;
            }
            int a = n / 3;
            int b = n % 3;
            if(0 == b){
                return (int)Math.pow(3,a);
            }else if(1 == b){
                return (int)Math.pow(3,a-1) * 4;
            }else{
                return (int)Math.pow(3,a) * 2;
            }
        }
    }

#### 复杂度分析 ####

*  时间复杂度：，实现中仅涉及取整、求余和求幂运算。
 *  空间复杂度：保存商数的变量 `a` 和保存余数的变量 `b` 仅使用常量空间。

### 二、动态规划 ###

当时，就分为两种情况：

1.  时，绳子只能剪为两个长度 1 的绳子，最大乘积为 1；
2.  时，绳子只能剪为长度为 2 和 1 的两段，最大乘积为 2；直接返回。

当 n > 3 时，就可以按照动态规划的逻辑进行处理了：

1.  初始值为：、、

为什么这么设置呢？

因为对于的绳子而言，我们完全可以拆分得到长度为 3、2 和 1 的绳子，拆分得到长度为 3 的绳子不必再拆分，算入乘积的话最大就是 3本身，2 和 1 同理。在举个栗子，比如，我们可以拆分为、和，而 3 、2 和 1 都是最终直接作为计算乘积时的因子出现的，所以.

1.  递推公式为：

对于长度为的绳子而言，要取得最大乘积，就需要知道它的前 3 个状态、和，而相应的最大乘积分别为：、和，的最大乘积则取三者中的最大值。

动态规划的递推公式为：

![format_png 5][]

#### 动画演示 ####

![format_png 6][]

#### 实现代码 ####

class Solution {
        public int cuttingRope(int n) {
             if(n <= 3){
                 return n-1;
             }
             int dp[] = {1,2,3};
             for(int i = 3; i < n; i++) {
              int tmp = Math.max(3 * dp[0],Math.max(2 * dp[1], 1 * dp[2]));
              dp[0] = dp[1];
              dp[1] = dp[2];
              dp[2] = tmp;
             }
             return dp[2];
        }
    }

#### 复杂度分析 ####

*  时间复杂度
 *  空间复杂度，使用的是长度为 3 的定长数组。

### 三、贪心方法 ###

按照贪心策略来剪绳子，当时，我们尽可能多地剪长度为 3 的绳子；当剩下的绳子长度为 4 时，把绳子剪成长度为 2 的两段绳子，因。

![format_png 7][]

#### 实现代码 ####

class Solution {
        public int cuttingRope(int n) {
          if (n <= 3) {
           return n-1;
          }
    
          int NumOf3 = n / 3;
          if (n - NumOf3 * 3 == 1) {
           NumOf3--;
          }
          
          int NumOf2 = (n - NumOf3 * 3) / 2;
          
          return (int)Math.pow(3, NumOf3) * (int)Math.pow(2, NumOf2);
        }
    }

#### 复杂度分析 ####

*  时间复杂度：
 *  空间复杂度：

## 知识点 ##

贪心思想、动态规划、数学推导

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，如果没有更新，说明我还在制作动画中^_^

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9vdzZwcnpadVBJRU5iMG01aWF3dXRJZjkwTjJVYjNkY1B1UDJLWEhKdmFSMUZ2MkZuaWNUdU95M0tjSHVJRUpiZDlsVXlPaWJlWHFXOHRFaG9KR0w5OHFPdy82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJzNWRiaDdnYm83QnJrMmtWZTlnTTVMTWtWdkRRdUtZYWZ0ZEJqalhCdUlpYmtsVlhoNUZxdUN3N09pY0lEMHFJalZlSEU1V3pnTEtvNHcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1ZjUyY3hYSEJMMHU1dkhWSmc0YjE5TTVUam50M3diY2Y0aWJrVzdidDJQT2NhQWliRTRtVUpKSVlqTVRMblFWM3dWZkdNSlFhSjFOTXcvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1ZjUyY3hYSEJMMHU1dkhWSmc0YjE5YVVpYmJydWhYSU5VMzZJU2ljaWMybFI2dXRkZkhtRktNZXgyVmJ5Y2hhcmhwNTdsbDEwUm9KaWFqdy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1ZjUyY3hYSEJMMHU1dkhWSmc0YjE5cGZXaWFWSGljVUVyRmliaWFkSkROVEcya21IYWxyS1lnVlVqQ0xONnpvSmp3ZFJ0RnBDUzY3emlhM3cvNjQw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1ZjUyY3hYSEJMMHU1dkhWSmc0YjE5cU9wdWcxaWNKdGpxUG1WU0dPQmJ3UnNZdGc1SFJOdXhPM1BDZXlWQ1V0aWFjMXBaWU5Cc0kwQlEvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9taWFabTA1NHZVaWJ1ZjUyY3hYSEJMMHU1dkhWSmc0YjE5NlFDaEE1WUltUlRJcGlhWHd0ZHdld1RNaWNDeldRaEhhRGpvbGJnVVVpY2R1b3BrWXpTZXdodThBLzY0MA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1ZjUyY3hYSEJMMHU1dkhWSmc0YjE5TjlKczA0bGljU01ZQ0c2YWR0SGVyN3k0OHZpYndhUko2cHRpY1ZIZnV3a1lsTm9PQ3JmUWx1N0FRLzY0MA?x-oss-process=image/format,png