题目链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
难度：中等

描述：
给你一根长度为 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。

题解

  1. class Solution:
  2.     def cuttingRope(self, n: int) -> int:
  3.         # 分成两段以上
  4.         # r[n] = max(r[n-1] * 1 + r[n-2] * 2 + ... + r[1] * (n-1))
  5.         # 分成两段
  6.         # r[n] = max(r[n], (n-1) * 1, (n - 2) * 2, ... , 1 * (n - 1))
  7.         r = [1] * (n+1)
  8.         for i in range(1, n+1):
  9.             for j in range(1, i):
  10.                 # 分成两段或多段
  11.                 r[i] = max(r[i], r[i-j] * j, (i - j) * j)
  13.         return r[n]