动态规划函数返回值异常及LeetCode环境下的奇怪返回问题

问题1：第一段代码返回18而非预期11 #

现象 #

给定测试用例triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]，预期返回最小路径和11（路径：2→3→5→1），但代码实际返回18。打印中间路径时能看到11，但最终取了错误的最小值。

原代码 #

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

错误原因 #

递归逻辑存在重复累加：

• path已经累加了当前层的元素tri[j][i]，但后续又将path与递归返回值（已包含下层到终点的路径和）相加，导致当前元素被计算两次。
• 例如路径2→3→5→1的正确累加是2 + (3 + (5 + 1))，但代码中变成2 + ( (2+3) + ( (2+3+5) +1 ) )，数值被严重放大。

修复代码 #

去掉冗余的path累加逻辑，让递归函数直接返回从当前位置(i,j)到终点的最小路径和：

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

def solve(tri, i, j):
    if j == len(tri) - 1:
        return tri[j][i]
    # 当前元素 + 下层两个路径的最小值
    return tri[j][i] + min(solve(tri, i, j + 1), solve(tri, i + 1, j + 1))

print(solve(triangle, 0, 0))  # 输出11

问题2：第二段代码返回float('inf')而非预期11 #

现象 #

LeetCode IDE中执行后，print('r', lowest)显示11，但函数最终返回float('inf')；本地PyCharm提示返回类型不匹配（声明返回int但可能返回float）。

原代码 #

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

错误原因 #

1. 冗余的lowest变量：solve函数本身已经返回了从起点到终点的最小路径和，完全不需要额外维护lowest变量。
2. 边界情况未处理：如果输入的triangle为空或只有一层，solve函数的递归逻辑不会执行到lowest = min(ans, lowest)这一行，导致lowest始终是初始值float('inf')。
3. 类型不匹配：float('inf')是浮点类型，与函数声明的返回类型int冲突，触发PyCharm的类型提示警告。

修复代码 #

直接返回solve函数的结果，同时处理边界情况：

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    if not triangle:
        return 0
    
    def solve(tri, i, j):
        if j == len(tri) - 1:
            return tri[j][i]
        return tri[j][i] + min(solve(tri, i, j + 1), solve(tri, i + 1, j + 1))
    
    return solve(triangle, 0, 0)

如果担心递归栈溢出（LeetCode测试用例可能包含大三角形），可改用动态规划迭代写法：

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    dp = triangle[-1].copy()
    for j in range(len(triangle)-2, -1, -1):
        for i in range(len(triangle[j])):
            dp[i] = triangle[j][i] + min(dp[i], dp[i+1])
    return dp[0]

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