为什么动态规划函数的返回值表现得很奇怪

Question

triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

def solve(tri, i, j, path):
    if j == len(tri) - 1:
        return tri[j][i]

    path += tri[j][i]
    path1 = path + solve(tri, i, j + 1, path)
    path2 = path + solve(tri, i + 1, j + 1, path)
    print(path1, path2)
    return min(path1, path2)


print(solve(triangle, 0, 0, 0))

answers 应该是 11，但它返回 18。从打印路径来看，很明显它确实得到了 11 的解，但它没有完全返回它。相反，代码继续执行并返回 18，这是最后两条路径中的最小值。我不明白为什么要这样做。

此外，我尝试修改代码，使其仅存储最低值（有点黑客攻击）。但这样做时，我遇到了一个更奇怪的问题：

def minimumTotal(triangle: List[List[int]]) -> int:
    lowest = float('inf')

    def solve(tri, i, j, path):
        if j == len(tri) - 1:
            return tri[j][I]

        path += tri[j][I]
        path1 = path + solve(tri, i, j + 1, path)
        path2 = path + solve(tri, i + 1, j + 1, path)
        ans = min(path1, path2)
        return and

    print('l', lowest)
    solve(triangle, 0, 0, 0)
    print('r', lowest)
    return lowest

print('ans', minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]]))

在这种情况下，执行求解函数后，“print('r', lower)”正确打印 11 作为答案。直接跟随的行是返回最低值。所以它应该返回最低值。但相反，它返回 float('inf')。但这只发生在leetcode IDE上（这题是leetcode 120，三角形）。我认为这一定与解决方案模板的类结构有关。然而，pycharm 确实告诉我“minimumTotal”函数“预期类型为‘int’，改为‘float’”作为返回值，因此它正在注册它返回无穷大。

Answer 1

您正在混合两种方法来执行深度优先遍历：

• 预购，您积累一条路径并将其传递，并在基本情况下返回该路径
• 后序，您让基本情况返回叶值，并在展开递归时将其累积到路径中。

但是您的代码混合了两者，因此会遭受重复计算：

path1

和

path2

代表一条完整路径，但在

return

语句返回其中之一之后，调用者会再次向此添加 path （它已经作为参数传递，并用于在那里构造

path1

和

path2

）。这是采用预购方式的更正版本：

def solve(tri, i, j, path):
    path += tri[j][i]
    if j == len(tri) - 1:
        return path
    path1 = solve(tri, i, j + 1, path)
    path2 = solve(tri, i + 1, j + 1, path)
    return min(path1, path2)

这是后序方法：

def solve(tri, i, j):
    val = tri[j][i]
    if j == len(tri) - 1:
        return val
    path1 = val + solve(tri, i, j + 1)
    path2 = val + solve(tri, i + 1, j + 1)
    return min(path1, path2)

请注意，此方法不需要路径参数，因为路径仅在进行递归调用后

才构造。

最后，这不是动态规划解决方案。它会多次使用相同的参数调用solve

，因此效率不高。要实现动态编程，您需要

制表

可以重用的结果。