CodingNinjas切杆分段问题递归解法错误排查及咨询

问题背景 #

我正在解决CodingNinjas平台的《Cut Into Segments》算法挑战，题目要求：给定表示杆长的整数N，需确定该杆能切成长度为X、Y或Z的段的最大数量。

我的代码如下：

def cutSegments(n, x, y, z):
    if n == 0:
        return 0  # No segments needed for a rod of length 0
    if n < 0:
        return float('-inf')  # Or a very large negative number

    a = cutSegments(n - x, x, y, z) + 1
    b = cutSegments(n - y, x, y, z) + 1
    c = cutSegments(n - z, x, y, z) + 1
    ans = max(a, b, c)
    
    if ans>0:
        return ans
    else:
        return 0

print(cutSegments(8, 3, 3, 3))

当输入为cutSegments(8, 3, 3, 3)时，预期输出为0（无法将8切成3的倍数段），但代码实际输出为2。请问我的解法存在什么错误？能否通过递归实现正确解法？

错误原因分析 #

你的代码核心错误在于最后判断ans>0时直接返回0的逻辑，这会把无效切割路径错误地标记为有效，导致上层递归累计出错误的段数。

以输入8,3,3,3为例：

1. 递归到n=2时，所有分支都会触发n<0的条件，返回-inf，此时ans=-inf，因为ans<=0返回0；
2. 回到n=5的递归层，三个分支都是0+1=1，ans=1>0返回1；
3. 回到n=8的递归层，三个分支都是1+1=2，最终返回2——但实际上8无法被3整除，根本没有有效切割方式。

问题出在：你把“无效路径返回的负数”和“有效路径的0（n=0时的合法返回）”混为一谈，用ans>0的判断直接返回0，让无效路径的结果被上层递归当成有效路径累加。

正确的递归实现 #

我们需要明确区分“有效切割”和“无法切割”的情况：

• 当n<0时，返回float('-inf')表示此路径完全无效，不能计入段数；
• 递归计算完三个分支后，如果最终的max_segments仍然是-inf，说明没有任何有效切割方式，返回0；否则返回max_segments。

修正后的代码：

def cutSegments(n, x, y, z):
    if n == 0:
        return 0
    if n < 0:
        return float('-inf')
    
    # 递归计算三种切割方式的最大段数
    a = cutSegments(n - x, x, y, z) + 1
    b = cutSegments(n - y, x, y, z) + 1
    c = cutSegments(n - z, x, y, z) + 1
    
    max_segments = max(a, b, c)
    
    # 所有路径都无效则返回0，否则返回有效段数
    return max_segments if max_segments != float('-inf') else 0

print(cutSegments(8, 3, 3, 3))  # 输出0，符合预期
print(cutSegments(9, 3, 3, 3))  # 输出3，正确
print(cutSegments(7, 2, 3, 5))  # 输出3（2+2+3），正确

可选优化：记忆化搜索 #

纯递归会存在大量重复计算（比如多次计算cutSegments(5)），可以加入记忆化缓存来优化时间复杂度：

def cutSegments(n, x, y, z, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    
    if n == 0:
        return 0
    if n < 0:
        return float('-inf')
    
    a = cutSegments(n - x, x, y, z, memo) + 1
    b = cutSegments(n - y, x, y, z, memo) + 1
    c = cutSegments(n - z, x, y, z, memo) + 1
    
    max_segments = max(a, b, c)
    memo[n] = max_segments if max_segments != float('-inf') else 0
    return memo[n]

print(cutSegments(8, 3, 3, 3))  # 输出0

内容的提问来源于stack exchange，提问作者Rahul Kumar