剪绳子

题目的主要信息：

• 把一根长度为$nn$的绳子分成$mm$段，每段长度都是整数
• 求每段长度乘积的最大值

举一反三：

学习完本题的思路你可以解决如下题目：

JZ83. 剪绳子（进阶版）

JZ71. 跳台阶扩展问题

JZ42. 连续子数组的最大和

方法一：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

一旦分出一段长度为1的小段，只会减少总长度，还不能增加乘积，因此长度为2的绳子不分比分开的乘积大，长度为3的绳子不分比分开的乘积大，长度为4的绳子分成2*2比较大。前面的我们都可以通过这样递推得到，后面的呢？

同样递推！如果我有一个长度为$nn$的绳子，我们要怎么确定其分出最大的乘积，我们可以尝试其中一段不可分的为$jj$，那么如果另一段$n-jn-j$最大乘积已知，我们可以遍历所有$jj$找到这个最大乘积。因此用$dp[i]dp[i]$表示长度为i的绳子可以被剪出来的最大乘积，那么后续遍历每个$jj$的时候，我们取最大$dp[i]=max(dp[i],j\ast dp[i-j])dp[i]\; =\; max(dp[i],\; j\; *\; dp[i\; -\; j])$就好了。

//可以被分成两份
for(int j = 1; j < i; j++)
    //取最大值
    dp[i] = max(dp[i], j * dp[i - j]);

具体做法：

• step 1：检查当number不超过3的时候直接计算。
• step 2：用dp数组表示长度为i的绳子可以被剪出来的最大乘积，初始化前面4个容易推断的。
• step 3：遍历每个长度，对于每个长度的最大乘积，可以遍历从1到$ii$的每个固定一段，按照上述公式求的最大值。
• step 4：最后数组最后一位就是答案。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int cutRope(int target) {
        //不超过3直接计算
        if(target <= 3) 
            return target- 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for(int i = 5; i <= target; i++)
            //可以被分成两份
            for(int j = 1; j < i; j++)
                //取最大值
                dp[i] = Math.max(dp[i], j * dp[i - j]);
        return dp[target];
    }
}

C++实现代码：

class Solution {
public:
    int cutRope(int number) {
        //不超过3直接计算
        if(number <= 3) 
            return number - 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        vector<int> dp(number + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for(int i = 5; i <= number; i++)
            //可以被分成两份
            for(int j = 1; j < i; j++)
                //取最大值
                dp[i] = max(dp[i], j * dp[i - j]);
        return dp[number];
    }
};

Python实现代码：

class Solution:
    def cutRope(self , number: int) -> int:
        #不超过3直接计算
        if number <= 3: 
            return number - 1
        #dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        dp = [0 for i in range(number + 1)]
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        dp[4] = 4
        #遍历后续每一个长度
        for i in range(5, number + 1):
            #可以被分成各种长度的两份
            for j in range(1, i):
                #取最大值
                dp[i] = max(dp[i], j * dp[i - j])
        return dp[number]

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，两层遍历
• 空间复杂度：$O(n)O(n)$，辅助数组dp的空间

方法二：贪心（扩展思路）

知识点：贪心

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

思路：

根据均值不等式，有：$\frac{n_1+n_2+\mathrm{.}\mathrm{.}\mathrm{.}+n_m}{m}\ge \sqrt[m]{n_1{n}_2\mathrm{.}\mathrm{.}\mathrm{.}{n}_m}\backslash frac\{n\_1+n\_2+...+n\_m\}\{m\}\backslash geq\; \backslash sqrt[m]\{n\_1n\_2...n\_m\}$，等号当且仅当$n_1=n_2=n_3=\mathrm{.}\mathrm{.}\mathrm{.}{n}_{m}n\_1=n\_2=n\_3=...n\_m$时成立，因为加法部分和是固定的绳子总长度，因此要使乘积最大，应该以相等的长度等分成多段。

如果将绳子按照每段长度为$xx$等分成$mm$段，则$n=mxn=mx$，乘积为$x^{m}x^m$，因为有$x^m=x^{\frac{n}{x}}=(x^{\frac{1}{x}}{)}^{n}x^m=x^\{\backslash frac\{n\}\{x\}\}=(x^\{\backslash frac\{1\}\{x\}\})^n$，因此当$x^{\frac{1}{x}}x^\{\backslash frac\{1\}\{x\}\}$取最大值时取最大值。

令$y=x^{\frac{1}{x}}y=x^\{\backslash frac\{1\}\{x\}\}$，即求这个函数的极值即可直到绳子等分成长度为多少可以使乘积最大。根据取对数、求导、求极值等一系列数学操作，得驻点为$x_0=ex\_0=e$，即极大值需要将绳子分成每段e，但是绳子长度只能是整数，靠近e的只有2 和3，二者分别代入公式，发现当$x=3x=3$是，乘积达到最大。

因此后续，使用贪心思想，不断将绳子分成每段长度为3即可，不足3的可以考虑，如果最后剩余的是2，直接乘上，如果最后剩余的是1，则取出一个3组成4分成长度为2的两段，因为$2\ast 2>1\ast 32*2>1*3$。

具体做法：

• step 1：按照上述思路，不超过3的直接计算
• step 2：超过3的不断累乘3，然后number不断减去3，直到最后不超过4。
• step 3：最后乘上剩余的数字。

Java实现代码：

public class Solution {
    public int cutRope(int target) {
        //不超过3直接计算
        if(target <= 3) 
            return target - 1;
        int res = 1;
        while(target > 4){
            //连续乘3
            res *= 3; 
            target -= 3; 
        }
        return res * target;   
    }
}

C++实现代码：

class Solution {
public:
    int cutRope(int number) {
        //不超过3直接计算
        if(number <= 3) 
            return number - 1;
        int res = 1;
        while(number > 4){
            //连续乘3
            res *= 3; 
            number -= 3; 
        }
        return res * number;
    }
};

Python实现代码：

class Solution:
    def cutRope(self , number: int) -> int:
        #不超过3直接计算
        if number <= 3: 
            return number - 1
        res = 1
        while number > 4:
            #连续乘3
            res *= 3 
            number -= 3 
        return res * number

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为绳子的长度，最坏需要计算$n\mathrm{/}3n/3$次
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间