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

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))

答案应该是 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)
        nonlocal lowest
        lowest = min(ans, lowest)
        return ans

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

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

Answer 1

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

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

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

path1并path2表示一个完整的路径，但是在return语句返回其中一个路径之后，调用者再次向其中添加a path（它已经作为参数传递，并用于构造path1和path2在那里）。

lowest第二个片段还有另一个问题：当输入只有一行时，它不会更新，例如triangle=[[2]]. 在这种情况下，基本情况会立即发生，并且solve无需设置就退出lowest。因此，该函数返回错误的答案，该答案也不是int，而是 float ( inf)。

这是采用预购方法的更正版本：

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使用相同的参数多次调用，因此效率不高。要实现动态编程，您需要将可重用的结果制成表格。

下面是动态规划解决方案的剧透：

def solve(tri): dp = [0] * (len(tri) + 1) for row in reversed(tri): dp = [min(dp[i], dp[i+1]) + val for i, val in enumerate(row)] return dp[0]