剑指offer--面试题68：剪绳子

题目描述

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

输入描述:

输入一个数n，意义见题面。（2 <= n <= 60）

返回值描述:

输出答案。

示例1

输入

返回值

Python实现：

class Solution:
    # 法1： 数学性质，总是切分成长度为3的段（num除以3），如果余数为2，就留一个长度为2的段
    # 如果余数为1，则减少一个长度为3的段，将减少的这个3和余数1凑一个2x2，即2个长度为2的段
    def cutRope2(self, number):
        # write code here
        if number < 2:
            return 0
        
        times_of_3, r = divmod(number, 3)
        if r == 2: # 余数为2
            times_of_2 = 1
        elif r == 1: # 余数为1
            times_of_3 -= 1
            times_of_2 = 2
        else:
            times_of_2 = 0
        return 3**times_of_3 * 2**times_of_2
    
    # 法2：动态规划
    def cutRope(self, number):
        # write code here
        # dp[i]表示长度为i的绳子经剪以后产生的最大乘积
        # 则dp[i] = max( dp[j]*dp[i-j] ), 1<j<i/2
        if number < 2:
            return 0
        if number <= 3:
            return number-1

        dp = [0]*(number+1)
        # 初始化
        dp[1] = 1 # 最短长度
        dp[2] = 2
        dp[3] = 3
        for i in range(4, number+1):
            _max = 0
            for j in range(2, i//2+1):
                _max = max(_max, dp[j]*dp[i-j])
            dp[i] = _max
        return dp[number]
    
    # 法3：递归，但是当number较大时（例如40）会超时
    def cutRope3(self, number):
        if number < 2:
            return 0
        if number <= 3:
            return number-1

        def helper(number):
            if number<=4:
                return number
            _max = 0
            for j in range(2, number//2+1):
                _max = max(_max, helper(j)*helper(number-j))
            return _max
        
        return helper(number)