把长度为n的绳子剪m段,每段长度乘积的最大值是多少
思路一:动态规划:
class Solution(object):
def maxProductAfterCutting(self,length):
"""
:type length: int
:rtype: int
"""
if length < 2:
return 0
if length == 2:
return 1
if length == 3:
return 2 #当长度小于3时,直接返回
li = [0,1,2,3] #列表存之前的最大值,当然这里1,2,3并不是表示最大值
for i in range(4,length+1):
max = 0
for j in range(1,i):
mul = li[j]*li[i-j]#体现递推公式
if mul>max:
max = mul
li.append(max)#增加最大值
return li[length]
思路二:贪婪算法:当n大于等于5时,尽可能剪长度为3的绳子,剩下的绳子长度为4时,把绳子剪成两段长度为2的绳子。