输出返回2而不是0

Question

这是我的 切入片段

给定一个整数“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))

此输出为 2（如何）

请帮助我也给我一个给定问题的递归解决方案

0 作为我的代码的输出

Answer 1

问题在于，当深度递归调用返回

-inf

时，您将其转换为0，因此上层递归调用会将其视为成功而不是失败，并为其添加1。

挑战在于，当 n 为 0 时，0

是一种成功，但是当持续失败 (

n < 0

) 时，你还需要最终返回 0。

为了做出这种区分，请用另一个简单的函数包装递归函数：只有该包装函数才会将

-inf

转换为 0:

def cutSegments(n, x, y, z):
    def recur(n):
        if n == 0:
            return 0
        if n < 0:
            return float('-inf')         
        a = recur(n - x)
        b = recur(n - y)
        c = recur(n - z)
        return max(a, b, c) + 1  # don't replace -inf with 0 here
        
    res = recur(n)
    return 0 if res < 0 else res # ...only here!

现在就可以了。尽管如此，它的效率仍然不是很高。你可以通过记忆来解决这个问题。一个简单的实现是使用

functools.cache

:

from functools import cache

def cutSegments(n, x, y, z):
    @cache
    def recur(n):
        if n == 0:
            return 0
        if n < 0:
            return float('-inf')         
        a = recur(n - x)
        b = recur(n - y)
        c = recur(n - z)
        return max(a, b, c) + 1
        
    res = recur(n)
    return 0 if res < 0 else res