难度: Medium
现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。
示例 1：
输入: bamboo_len = 12 输出: 81提示：
2 <= bamboo_len <= 58
注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/
Submission
运行时间: 52 ms
内存: 14.8 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)
Explain
该题解采用了动态规划的思路来解决问题。函数 `dp(i)` 表示长度为 `i` 的竹子能得到的最大乘积。基本情况是当竹子长度为 2 时，只能分为两段，每段长度为 1，乘积为 1。对于长度大于 2 的竹子，我们尝试每种可能的分割方式（即从长度 2 到 i-1），并计算两种情况：1) 将竹子分割为 j 和 i-j，继续分割 i-j；2) 将竹子分割为 j 和 i-j，但不再分割 i-j。这两种情况中的最大值会被存储在 memo 字典中，以避免重复计算。最后返回长度为 n 的竹子的最大乘积。
时间复杂度: 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
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) # 计算并返回最大乘积
Explore
动态规划适用于这类问题因为它可以通过解决子问题来构建对整个问题的解答，并且这些子问题往往重叠，即多次出现在问题的不同部分。在砍竹子的问题中，最优切割方式可能需要考虑所有可能的分割组合，动态规划通过存储这些子问题的解（memoization）避免重复工作，从而提高效率。相比之下，贪心算法在每一步只采取局部最优解，可能无法得到全局最优解，特别是在分割决策互相影响时。其他算法如回溯或分治可能效率较低，因为它们没有利用子问题解的重复性，可能导致计算量大增。
在函数 `dp(i)` 中，`max(j * dp(i - j), j * (i - j))` 的两种情况分别代表：1) 将竹子首先切割为长度为 `j` 和 `i-j` 的两段，其中 `i-j` 部分继续进行最优分割，即 `dp(i-j)` 表示对长度为 `i-j` 的竹子继续进行分割所能得到的最大乘积。2) 将竹子切割为长度为 `j` 和 `i-j` 的两段，但是 `i-j` 部分不再进行分割，直接考虑这两段的乘积 `j * (i - j)`。这样的分割策略确保了所有可能的分割方式都被考虑，从而找到最大的乘积值。
在实现中选择从 `2` 到 `i-1` 进行迭代是因为：当 `j=1` 时，剩余部分 `i-1` 与 `1` 相乘，实际上没有改变值，即 `1 * (i-1) = i-1`。这意味着这种分割并没有带来任何增值，仅仅是将竹子分成了长度为 1 和 `i-1` 的两部分，与不分割相比没有任何乘积上的增益。因此，从 `j=2` 开始迭代既可以避免无效的计算，也保证了每次分割都可能带来乘积的增加。