python官方题解--剪绳子(3种解法)

此题作为面试中经常考到的类型,涉及到我们熟悉的递归,动态规划,贪婪算法这三种,此文会介绍这三种解法.

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

   #递归写法
   class Solution:
    def cutRope(self, number):
        # write code here
        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:
            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. 下面介绍动态规划的解法,接着上面的递归解法我们可以将其转换成动态规划的写法.由于这是一个从上至下的递归公式,递归会出现很多大量不必要的计算,一个很好的方法就是按照从下而上的顺序计算,即:
   我们先得到f(2),f(3),再得到f(4),f(5),直到f(n).
   我们可以得知f(2)=1, f(3)=2
   下面就可以写我们的代码啦:

   #动态规划
   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 = [0]*(number+1)
        #定义前几个初始变量的值
        products[0] = 0
        products[1] = 1
        products[2] = 2
        products[3] = 3
        #进行动态规划,也就是从下向上的进行求解
        for i in range(4, number+1):
            max_ = 0
            for j in range(1, i/2+1):
                max_ = max(products[j]*products[i-j], max_)
            products[i] = max_
   
        max_ = products[number]
        return max_

3.下面介绍贪婪算法,我目前对这个不是很了解,需要一定的数学功底,只能先贴出代码,望大家谅解:

#贪婪算法
class Solution:
    def cutRope(self, number):
        # write code here
        if number < 2:
            return 0
        if number == 2:
            return 1
        if number == 3:
            return 2       
        #申请辅助空间
        timesOf3 = number / 3
        if (number - timesOf3*3) == 1:
            timesOf3 -= 1
        timesOf2 = (number - timesOf3*3) / 2
        return pow(3, timesOf3)*pow(2, timesOf2)