剑指67-剪绳子

Posted on | In |

题目描述

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

1
2
3
4
5
6
7
8
输入描述:
> 输入一个数n，意义见题面。（2 <= n <= 60）
输出描述:
> 输出答案。

示例1
输入 > 8
输出 > 18

动态规划，递归。用函数cut(number)剪长度为number的绳子，由于m、n都是正整数，第一次调用cut和其后的调用有区别

  • 第一次调用必须非要把绳子至少一分为二为两个短绳子，对短绳子再次调用该cut函数，则可能会继续剪也可能不再继续剪。比如2第一次调用，必须要拆分成1和1；然而3的第二次调用也有的这个2，但是可以拆也可以不拆。 所以，cut函数内部要根据其是否是首次调用，分为两种情况处理。
  • 由于number必然是整数，因此动态规划程序里可以用一个数组来保存子问题的结果。具体的，用长度为number+1的数组cutlog来记录非首次调用cut函数的返回值，cut(number)返回值用cutlog[number]来表示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def cutRope(self, number):
        self.cutlog = [0]*(number+1) #记录非首次cut函数调用的返回值
        self.cutlog[0] = self.cutlog[1] = 1
        def cut(number, isDoor = False):
            if not isDoor:
                res = []
                for n in range(1, number+1):
                    if self.cutlog[number-n] == 0:
                        self.cutlog[number-n] = cut(number-n)
                    res.append(n*self.cutlog[number-n])
            else:
                if number <= 1:
                    return None
                res = []
                for n in range(1, number):
                    if self.cutlog[number-n] == 0:
                        self.cutlog[number-n] = cut(number-n)
                    res.append(n*self.cutlog[number-n])
            return max(res)
        return cut(number, isDoor=True)