14. 剪绳子

• 利用动态规划，需要O(n^2)时间和O(n)空间，也就是利用一个表，储存长度为1~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
     products = [0, 1, 2, 3]
     for i in range(4, number+1, 1):
         product = 0
         for j in range(1,4//2+1,1):
             res = products[j]* products[i-j]
             product = max(res,product)
             products.append(product)
     return  products[-1]

• 贪婪算法：这种想法比较巧妙，尽量把大于5的数分解成3的乘积，如果剩下的长度为4，则把4分解成2和2，因为3 1 < 2 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
     timesof3 = number // 3
     if number - timesof3 * 3 == 1:
         timesof3 -= 1
     timesof2 = (number - timesof3 * 3) / 2
     return (3**timesof3)*(2**timesof2)