本题有三种解法：递归，递归 + 数组存储 与 动态规划。方法与 “剑指 Offer - 斐波那契数列” 类似，可以一起复习 （指路：https://jianengli.github.io/2020/12/28/jianzhi_offer/array/jz7/）。

Question source

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

1. 递归

我们先定义函数f(n)为把绳子剪成若干段之后的各段长度乘积的最大值.在剪第一刀的时候,我们会有n-1种可能的选择,也就是说剪出来的第一段绳子的长度可能为1,2,......n-1.因此就有了递归公式 f(n) = max(f(i)*f(n-i)),其中0< i < n.

好写，但会超时。

Complexity

  • 时间复杂度：O(n!)
  • 空间复杂度：O(n), 最多分n段，每段长度为1， 所以递归深度为n
图一：递归图解

显然，从图片中可以看到，f(5)重复计算了2次，f(4)重复计算了3次，可想而知，越往上，那么重复计算的次数会越多。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def cutRope(self, number):
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2      
        return self.cutRopeCore(number)

    def cutRopeCore(self, number):
        if number < 4: # 注意： 缺少这个判断会出错；递归中number为前4个时，不是解(解要求m>=1),而是m可以为0时的解，也就是服务于递归的初始条件；number为0，1，2，3时，满足m>=1时，解在cutRope（）中
            return number
        max_ = 0
        
        for i in range(1, number/2+1):
            max_ = max(self.cutRopeCore(i) * self.cutRopeCore(number - i), max_)
        return max_

2. 记忆法递归

新建数组保存中间值，避免重复计算。如图一可见。

步骤如下：

  1. 初始化一个大小为 n+1 的数组，初始值为 -1 ，也可以-2， 反正是不可能在乘积中存在的值。

  2. 在方法一的代码上，添加部分代码。

Complexity

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# -*- coding:utf-8 -*-

class Solution:
    def cutRope(self, number):
        # write code here
        if number<2:
            return 0
        if number==2:
            return 1
        if number == 3:
            return 2      

        # 在法1基础上添加
        check_list=[-1]*(number+1)

        return self.cutRopeRecursion(number,check_list)
    
    def cutRopeRecursion(self,number,check_list):
        if number < 4:
            return number

        # 在法1基础上添加
        if check_list[number]!=-1:
            return check_list[number]

        max_product = 0
        for i in range(1,number//2+1):
            max_product = max(self.cutRopeRecursion(i,check_list)*self.cutRopeRecursion(number-i,check_list),max_product)

        # 在法1基础上添加
        check_list[number] = max_product

        return check_list[number]

思考：cutRope（）中的if number==2 and 3 没有时，其实方法1和2都能通过；考虑到很多解法写入了这些，我就保留了。但 cutRopeRecursion（）中if number <=4 一定要保留。也就是说，递归函数的终止条件: 如果n <= 4, 显然 cutRopeRecursion(n，check_list) = n --是不能缺少的。

3. 动态规划

拿一个list列表去存下来已经计算好的乘积f(n)，然核心思想就是动态规划。

下面介绍动态规划的解法,接着上面的递归解法我们可以将其转换成动态规划的写法。由于上面思路是基于从上至下的递归，递归会出现很多大量不必要的计算。一个很好的方法就是按照从下而上的顺序计算,即:

我们先得到f(2),f(3)，再得到f(4),f(5)，直到f(n)。

Complexity

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)

Code

class Solution:
    def cutRope(self, number):
        # write code here
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2   
        
        products=[-1]*(number+1) 
        
        products[0]=0
        products[1]=1
        products[2]=2
        products[3]=3
        
        for i in range(4,number+1):
            max_product = 0
            for j in range(1,i//2+1):
                max_product = max(products[j]*products[i-j],max_product) # 注意 不是 max(j*i-j,max_product)
            products[i] = max_product #不断的将计算好的乘积保存至数组
        return products[number]

思考：

总的来说，方法一是基础。方法二，方法三都是在方法一的基础上修改的。

Q:接下来，我们就可以开篇的问题了，什么样的题适合用动态规划？

A：一般，动态规划有以下几种分类：

  1. 最值型动态规划，比如求最大，最小值是多少

  2. 计数型动态规划，比如换硬币，有多少种换法

  3. 坐标型动态规划，比如在m*n矩阵求最值型，计数型，一般是二维矩阵

  4. 区间型动态规划，比如在区间中求最值

其实，根据此题的启发，我们可以换种想法，就是什么样的题适合用暴力递归？

显然就是，可能的情况很多，需要枚举所有种情况。只不过动态规划，只记录子结构中最优的解。

4. 贪心算法

如果target大于3，那么要求出的乘积的最大值一定是被剪裁过的（4看作2 * 2），要使结果积的数值最大，要避免剪裁出来1的情况，而又已知了当这个数值大于3时，要经过剪裁才能获取最大值，可以得出结论这个数值是被剪裁为2和3的，而且尽量剪裁3（如6：2 * 2 * 2与3 * 3，9：3 * 3 * 3，2 * 2 * 2 * 3）。

Complexity

  • 自测结果显示，时间复杂度和空间复杂度比方法2，3稍微高些。

Code

class Solution:
    def cutRope(self, number):
        # write code here
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2      
        # 申请辅助空间
        # 如果number能够被3整除的话，就把这个数分解为3，也就是pow(3, timesOf3)；如果余数为1，就分解出来2个2，其余为3；如果余数为2，就分解出来一个2其他为3
        timesOf3 = number / 3
        if (number - timesOf3*3) == 1:
            timesOf3 -= 1
        timesOf2 = (number - timesOf3*3) / 2
        return pow(3, timesOf3)*pow(2, timesOf2)