剑指Offer：面试题14（1）和（2），剪绳子（动态规划思路详解）

短命女 2023-02-15 13:51 29阅读 0赞

# 题目1： #

> 给你一根长度为 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

### 一、不严格的数学法 ###

题目很好理解。

这个题开始没想到别的，就想着数学归纳，因此列举了一下前面的情况：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]  
到这里就可以总结出来：

##### 当N一旦开始>4，最大乘积都是2和3的组合； #####

*  有3尽量分3。
 *  如果分为3后没余数，那正好；
 *  如果分完3余1，那浪费了，就拿出一个3和余的1组成两个2；
 *  如果分为3后余2，那就乘2。

所以顺这个思路就可以把代码写出来：

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

提交通过。

这其中有数学证明，关于在和一定的情况下，分配，再求乘积，这样一个函数，求导，求最值一系列操作，最终得到结果是，我们的思路是正确的。

还可以稍作修改，写出更简短的代码：

class Solution {
        
        public int cuttingRope(int n) {
        
            if(n<2){
        
                return -1;
            }
            if(n<4){
        
                return n-1;
            }
            if(n==4){
        
                return 4;
            }
    
            int ans=1;
            while(n>4){
        
                ans*=3;
                n-=3;
            }
    
            return n*ans;
    }

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

这是一个**在一定约束条件下** 求 **最大值**，属于最优化问题，很容易想到动态规划。

接着我们直接大胆的定义dp，千万不要多想：

**用 dp\[ n \] 来表示长度为 n 的绳子剪断后，乘积的最大值**（假设n>2）  
（注意这个dp的定义，直接就表示的是乘积结果），那么状态转移方程是什么呢？

1.  先对绳子一刀下去，剪的位置有 为1~n-1 个可能，记为 j ；
2.  分开的这两段绳子，要不要剪、从哪里剪、对应的乘积最大值是多少，这是两个长度为\[ j \] 和 \[ n-j \] 的绳子的**子问题**，这里我们也就找到了动态规划的最优子结构。

也就是说，我们直接考虑这个绳子 n ，一刀一刀的划分，然后划分的各部分会带来一个乘积结果。划分过程从整体到部分。

因此我们可以得到状态转移方程：

**dp\[n\] = max( dp\[j\] \* dp\[ n - j\] )**

> 解释：对于长 n 的绳子来讲，就是要分两段的乘积最大，对于这两段子绳子的乘积要最大，他们分别的乘积也要最大……  
>   
> 而每一次分割的点 j 有 1~n-1 种可能。（事实上我们只用到 n/2 就够了，超过一半之后 两边只是互换了长度。）

这样，有了动态规划的状态定义，状态转移方程，我们再来定义动态规划的边界，也就是**最小子问题**的解：

*  dp\[1\]=1代表在dp的子问题里，子绳子长度为1给乘积带来的最大收益是1
 *  dp\[2\]=2代表在dp的子问题里，子绳子长度为2给乘积带来的最大收益是2
 *  dp\[3\]=3;代表在dp的子问题里，子绳子长度为3给成绩带来的最大收益是3

对于n<4的情况，最大乘积分别是：**n=1 max无意义；n=2 max=1；n=3，max=2.**

这显然是和dp里面的初始值定义有出入。

但是我们思考一下就会发现，通过求解得出的dp数组是，从n=4开始才有意义的。  
**因为在 n<4 的时候，我们不得不切割，从而乘积变小；  
而一旦 n>=4，我们可以选择切割，也可以选择不切割，当不切割的时候带来的乘积收益大，我们当然选择不切割，也就是 dp\[2\]=2 , dp\[3\]=3 的意思。**

（这里对于数学方法里对 3 和 2 的合理性，也有一点帮助？）

最后写出代码：

class Solution {
        
        public int cuttingRope(int n) {
        
            if (n < 2) {
        
                return 0;
            }
            if (n == 2){
        
                return 1;
            }
            if (n == 3){
        
                return 2;
            }
            
            int[] dp=new int[n+1];
            //接下来的四个初始值不会用到，只是为了方便计算
            dp[0]=0;
            dp[1]=1;//在dp的子问题里，子绳子长度为1最好的方法是不分割
            dp[2]=2;//在dp的子问题里，子绳子长度为2最好的方法是不分割
            dp[3]=3;//在dp的子问题里，子绳子长度为3最好的方法是不分割
            int tempMax=0;
            for(int i=4;i<=n;i++){
        
                for(int j=1;j<=i/2;j++){
        
                    tempMax=Math.max( dp[j]*dp[i-j] , tempMax);
                }
                dp[i]=tempMax;//填入dp数组
                tempMax=0;//每次更新，下轮方便进行全新划分
            }
    
            return dp[n];
        }
    }

### 三、暴力法 ###

一个数学基础知识是，指数函数的增长是疯狂的，所以平均分成一样的组合，乘积结果一定大于其他形式的组合。

那么**对于长度为n的绳子，剪成 m 段，每一段平均分成长度是 n/m 的子段，乘积就会最大。**

> 剪成 m 段是不固定的，可以从 2 到 n。  
> 每一段可能不是整数，因此需要做处理。

如此暴力循环，直接更新最大值，就得到了答案。

下面我们看一看对于 n/m 结果为非整数的处理：

*  对于长度为 **n** 的绳子，剪成 **m** 段，每段长度 **subN = n/m** ；
 *  **subN**只取整数，那么剩下待分配的长度就是 **left = n%m**;
 *  把剩下的尽量均匀分配，（也是同样由于上面的数学知识），就会有 **left** 个**长度为 subN+1** 的绳子，以及 **m-left 个长度为 subN** 的绳子。

> 比如长为 7 的绳子， 剪成 4 段，每段 subN = 1，剩下 3 需要进行分配，那么已经分配的 4 段里 会有 3 段变成 1+1=2，还有 4-1 段仍然是 1。

代码也很简单：

class Solution {
        
        public int cuttingRope(int n) {
        
            int ans=0;
    
            //可以分成 2~n 段,遍历所有可能
            for(int i=2;i<=n;i++){
        
                //对于每次平均分段，计算乘积
                ans=Math.max( cut( n , i ) , ans );
            }
            return ans;
        }
    
        //尽量平均分绳子的方法
        public int cut(int n,int m){
        
            int subN=n/m;//平均每段
            int left = n%m;//剩下的长度
    
            //有left个 subN+1 , 有 m-left 个还是subN
            int result = (int)( Math.pow(subN+1, left) * Math.pow(subN, m-left) );
    
            return result;  
        }
    }

# 题目二 #

> 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m-1\] 。  
> 请问 k\[0\]\*k\[1\]\*…\*k\[m-1\]可能的最大乘积是多少？  
>   
> **答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 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 <= 1000**

##### 和上一道题目没有任何区别，但是n的范围变大了，也就是说可能带来的结果出现溢出，（n=100的时候如果分成50段2，那2^50都显然大于int 的范围了，更不用说1000）因此说了要做取模的处理。 #####

### 一、数学法 ###

回看上面的代码：

int size=n/3;
            int left=n-size*3;
            if(left==2){
        
                return (int)Math.pow(3,size)*2;
            }else if(left==0){
        
                return (int)Math.pow(3,size);
            }else{
        
                return (int)Math.pow(3,size-1)*4;
            }

这个方法：中间的指数幂相乘中，直接调用Math.pow()方法也是不行的，一方面Math.pow会产生精度误差；另一方面，这个方法是double类型的参数，double是8个字节，64位，显然计算结果也会溢出，哪怕最后再取模，答案也不对了。

那么我们来看第二种数学方法，分成3为一份的子绳，循环逐渐求积：

int ans=1;
            while(n>4){
        
                ans*=3;
                n-=3;
            }
    
            return n*ans;

在上一道题里，这样是可行的，但是中间相乘的时候会遇到溢出问题，但是好的一点是，不像math.pow()方法，这个过程我们可以在中间干预。

而**求余**运算的性质又让我们能够，在中间\*3的每一次都取一次余，这样和最后的结果取余一次是一样的。

所以只要在中间步骤加入简单的变化，就能得到结果：

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

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

动态规划的核心代码是：

for(int i=4;i<=n;i++){
        
                for(int j=1;j<=i/2;j++){
        
                    tempMax=Math.max( dp[j]*dp[i-j] , tempMax);
                }
                dp[i]=tempMax;//填入dp数组
                tempMax=0;//每次更新，下轮方便进行全新划分
            }

更新 dp 数组是**基于比较**的，而数据中间会溢出，所以比较会失效，显然不能用了。

要想能够继续比较，当然可以使用 **java 的 BigInteger** 类来保存中间结果，这样直接调用它的max方法就可以进行比较了。

import java.math.BigInteger;
    
    class Solution {
        
        public int cuttingRope(int n) {
        
            if (n < 2) {
        
                return 0;
            }
            if (n == 2){
        
                return 1;
            }
            if (n == 3){
        
                return 2;
            }
    
            BigInteger[] dp = new BigInteger[n+1];
            dp[0] = new BigInteger("0");
            dp[1] = new BigInteger("1");
            dp[2] = new BigInteger("2");
            dp[3] = new BigInteger("3");
            BigInteger tempMax= new BigInteger("0");
            for(int i=4; i<=n; i++){
        
                for(int j=1; j<=i/2; j++){
        
                    tempMax=tempMax.max(dp[j].multiply(dp[i-j]));
                }
                dp[i]=tempMax;
                          tempMax=0;
            }
            return dp[n].mod(new BigInteger("1000000007")).intValue();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200605214032716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70