1. Title Description

I'll give you a length of n Rope , Please cut the rope into m paragraph （m、n Are integers. ,n>1 also m≥1）. The length of each piece of rope is marked as k[0]、k[1]、……、k[m].k[0]k[1]…*k[m] What's the maximum possible product ？ For example, when the length of the rope is 8 when , We cut it into lengths of 2、3、3 Three paragraphs of , At this point we get the maximum product 18.

2. Ideas

2.1 Dynamic programming

Dynamic programming , First, analyze from the top down , In the length of n For the rope of f(n), The remaining two lengths after a cut are i and n-i, It's possible to continue to decrease ( Sub problem ), therefore ：

And then solve the problem from the bottom up , It can be downloaded from f(1) Start counting up and save , Finally get f(n) Value .
Because when i Greater than n//2 when , You don't have to calculate , In fact, the calculation is repeated :

2.1 Dynamic programming code

def cutRope(length):
if length == 0:
return 0
if length == 1:
return 1
if length == 2:
return 2
if length == 3:
return 3
if length == 4:
return 4
result = [0,1,2,3]
for i in range(4,length+1):
max = 0
for j in range(1,i//2+1):
temp = result[j] * result[i-j]
if temp > max:
max = temp
result.append(max)
return result[length]
print(cutRope(8))
# The output is 18

2.2 The law of greed

Equal sign in n=5 It was established .
So cut the rope as much as possible 3, Let the rest be 2 This combination .

2.2 python Code

def cutRope(length):
if length <= 4:
return length
timeOfThree = length // 3
if length - timeOfThree * 3 == 1:
# If you subtract 3, There is still left 4, You can't subtract at this point 3 了 ,2*2 > 3 * 1
timeOfThree -= 1
timeOfTwo = (length - timeOfThree * 3) // 2
return pow(3,timeOfThree) * pow(2,timeOfTwo)
print(cutRope(8))
# The output is ：18