难度: Medium
现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：bamboo_len = 12 输出：81
提示：
2 <= bamboo_len <= 1000注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/
运行时间: 1312 ms
内存: 16 MB
class Solution:
def cuttingRope(self, n: int) -> int:
memo = dict()
def dp(i):
if i == 2:
return 1
if i in memo:
return memo[i]
res = 0
for j in range(2, i):
res = max(res, max(j * dp(i - j), j * (i - j)))
memo[i] = res
return memo[i]
return dp(n) % 1000000007
题解使用了自顶向下的动态规划方法，并利用记忆化来存储已经计算过的结果，避免重复计算，提高效率。函数dp(i)的作用是找到长度为i的竹子能得到的最大乘积。基本情况是当i等于2时，最大乘积为1。对于i大于2的情况，我们通过尝试每一种可能的第一段长度j（从2到i-1），计算两种情况的最大值：一是将竹子剩余部分继续切割得到的最大乘积(j * dp(i - j))，二是直接将竹子切成j和i-j两段(j * (i - j))。这两种情况的最大值，即为当前i的最大乘积。这样的递归确保我们可以从已解决的子问题构建出更大问题的解答。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def cuttingRope(self, n: int) -> int:
memo = dict() # 初始化字典用于记忆化存储
def dp(i):
if i == 2:
return 1 # 当长度为2时，只有一种切割方法，乘积为1
if i in memo:
return memo[i] # 如果结果已经计算过，直接返回结果，避免重复计算
res = 0 # 初始化最大乘积为0
for j in range(2, i): # 遍历所有可能的第一段长度
res = max(res, max(j * dp(i - j), j * (i - j))) # 计算不继续切和继续切的最大乘积
memo[i] = res # 存储计算结果
return memo[i] # 返回当前长度的最大乘积
return dp(n) % 1000000007 # 返回结果并取模
自顶向下的动态规划方法，也称为记忆化递归，从最终目标开始解决问题，逐步分解为较小的子问题。该方法的优点在于只解决实际需要的子问题，节省计算资源，特别是当部分子问题不必解决时。缺点是递归调用可能导致较大的栈开销，且递归结构可能在理解和调试上更复杂。相对地，自底向上的方法，即迭代方法，从最小的子问题开始，逐步构建解决方案直至达到最终目标，通常在空间效率上更优，易于理解和实施，但可能会计算一些不必要的状态。
在函数`dp(i)`中, `j * dp(i - j)`考虑的是将长度为i的竹子切成长度为j和i-j的两段，其中长度为i-j的段继续进行切割以获取最大乘积。而`j * (i - j)`则是将竹子直接切成两段，不对长度为i-j的段进一步切割。这两种情况的区别在于是否继续对剩余部分进行优化切割。比较这两种情况是为了确保在每一步都能获得可能的最大乘积，无论是继续切割或是停止切割。
在计算最大乘积时，从2开始循环到i-1是因为至少需要切割出两段，每段最小长度为1。若考虑将i本身作为一段，则不会有任何切割发生，这与题目要求找到切割后的最大乘积相违背。因此，我们不考虑将整个i作为一段的情况，而是寻找至少一次切割的最优解。
在取模操作（% 1000000007）中，加入这一步是为了防止结果数值过大而超出整数表示范围，特别是在涉及大数的程序设计语言中。1000000007是一个大质数，常用于避免溢出同时减少计算结果的碰撞概率。直接返回dp(n)的结果可能导致整数溢出，从而得到错误的输出。取模操作确保结果保持在安全的数值范围内。