面试题14：剪绳子

题目 ：给你一根长度为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。

方法：
第一种思路：使用动态规划方法，这种方法的时间复杂度是O(n*n)，空间复杂度是O(n)。简单描述下动态规划可以解决的问题的特点：

① 问题求的是一个最优解；
②整体问题的最优解依赖各个子问题的最优解；
③大问题分解成各个小问题后，这些小问题之间还有相互重叠的更小子问题；
④为了避免重复求解重复的子问题，一般从上往下分析问题，从下往上求解问题。

第二种方法为贪婪算法，每步都做一个贪婪的选择，需要较好的数学功底，笔者暂时还没有理解这种做法的思想，待补充。

算法思路：
使用动态规划，本题目的每一步都面临若干个选择，我们不知道哪个选择最好，因此要逐一进行计算并得出最优，用数学语言来表达则为f(n)=f(i)*f(n-i)，此外，需要将最小的特殊问题进行考虑，分别为n=2，3时。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def cutRope(self, number):
        # write code here
        if number == 2:
            return 1
        if number == 3:
            return 2
        products =[0]*(number+1) 
        #如果不生成全0列表，则选择后面使用append赋值，因为python不能对不存在的位置进行'＝' 操作
        products[1] = 1
        products[2] = 2
        products[3] = 3

        for i in range(4,number+1):
            max_result = 0
            for j in range(1,i//2+1):
                product = products[j]*products[i-j]
                if max_result < product:
                    max_result = product
            products[i]=max_result

        return products[number]

运行结果：

运行结果.png