动态规划

剪绳子

题目

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

思路

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

代码

class Solution:
 
    def cutRope1(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_
    
    def cutRope(self, number):
         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_