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、k、……、k[m].kk…*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.
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 :
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
Equal sign in n=5 It was established .
So cut the rope as much as possible 3, Let the rest be 2 This combination .
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