题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
image.png

思考

长度为1，不能剪，最大乘积是1；
长度为2，不能剪，最大乘积是2；
长度为3，不能剪，最大乘积是3；
长度为4，不能剪，最大乘积是4；
长度为5，剪，只有一种情况（2， 3），最大乘积为6。

设绳子长度为n时，剪成任意段的后的最大乘积为dp[n]。
当 n <= 4, dp[n] 为 n；
当 n == 5, dp[n] = 6
当 n == 6, dp[n] = max(dp[n-i] * dp[i])，i为2，…, n-2

image.pngimage.pngimage.png

代码

  1. class Solution:
  2.     def cuttingRope(self, n: int) -> int:
  3.         if n < 4:
  4.             return n-1
  7.         dp = [0]*(n+1)
  8.         dp[2] = 2
  9.         dp[3] = 3
  10.         # dp[4] = 4
  11.         # dp[5] = 6
  13.         for i in range(4, n+1):
  14.             dp[i] = 0
  15.             for j in range(2, (i//2)+1):
  16.                 dp[i] = max(dp[i-j] * dp[j], dp[i])
  17.             # print(dp[i])
  19.         return dp[n]