时间戳

首页 > 解决方案 > 使用递归的最小成本路径

python - 使用递归的最小成本路径

问题描述

我尝试使用递归而不是动态编程找到最小成本路径，不幸的是结果不对，我尝试自己调试代码，递归太多，我无法遵循。

A = [[6,2,4,1],
    [1,2,5,4],
    [2,7,3,2],
    [1,2,2,5],
    [9,5,1,6]]

使用上述矩阵和起点 A[0][1]，MCP = 2,1,2,2,1 = 7

允许的方向只有向下和对角线（从上到下）

我的代码结果 3：

def minSumRekursive_helper(A, n ,c):

    max_n = len(A)
    max_c = len(A[0])

    if (n >= max_n or c < 0 or c >= max_c):
        return 0

    minSum = min(
        minSumRekursive_helper(A, n+1, c-1),
        minSumRekursive_helper(A, n+1, c+1),
        minSumRekursive_helper(A, n+1, c)
    )

    total = A[n][c] + minSum
    return total

如果有人可以帮助我，上面的代码哪里出错了？，我很感激。

标签： pythonrecursion

解决方案

您的代码中的问题来自这两行：

if (x >= max_x or y < 0 or y >= max_y):
        return 0

您在此if语句中混合了两种不同的条件：

  • 如果x >= max_x，则表示我们已经到达目的地；
  • 如果y < 0 or y >= max_y，那意味着我们撞到了墙上。

这是两种截然不同的情况，返回值应该不同。所以我建议将这两种情况分成两个if陈述，并仔细考虑return在这两种不同情况下要做什么。

备注：您的代码使用x纵坐标和y横坐标，这与世界上其他人正在做的相反。计算执行代码并不关心这种或另一种方式，但未来阅读代码的人会关心。我建议交换两个字母。

推荐阅读