• 利用动态规划,需要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)