递归地通过二维二进制数组并计算要通过的“1”的数量

Question

我正在尝试学习编程，而我真正难以理解的一个概念是递归。

编辑：下面是 link 实际问题的图像，它更好地解释了说明。我认为我的解释不是最好的。

Instructions

我正在尝试在 python 上使用递归编写一个程序，该程序采用 A[0,...,n-1][0,...,n- 的二维二进制数组1] 和 returns 到达终点必须通过的最小“1”数。起点是A[0][0]，终点是A[n-1][n-1]。您一次只能移动一个单元格，方法是向右移动一个单元格或向下移动一个单元格。该数组仅包含 0 和 1。它类似于一个迷宫，其中必须穿过 0，而 1 充当一堵墙，但在这里人们可以而且很可能需要穿过几个 1。输出将是到达终点所需通过的最少 1 数。

我不确定这是否是正确的方法。我认为使用 1 函数可能会更好。我似乎也无法弄清楚如何计算必须通过的危险区域的数量。我想你可能会注意到我是新手，如果有人能引导我朝着正确的方向前进，我将不胜感激。

def minCellsTravel(grid):

    gridWidth = len(grid[0])
    gridHeight = len(grid)

    def helperFn(row, col):

            # if we already reached the rightmost end
            if row == gridHeight-1 and col == gridWidth-1:
                    return grid[row][col]

            start = grid[row][col]
            downMove = None
            if row < gridHeight - 1:
                    downMove = start + helperFn(row + 1, col)

            rightMove = None
            if col < gridWidth - 1:
                    rightMove = start + helperFn(row, col + 1)

            if rightMove and downMove:
                    return min(rightMove, downMove)
            elif rightMove:
                    return rightMove
            else:
                    return downMove

Answer 1

像这样应该可以解决问题

def solve(row, col, A):

    if (row == A.shape[0] - 1) and (col == A.shape[1] - 1):
        return A[row][col]
    if (row >= A.shape[0]) or (col >= A.shape[1]):
        return A.shape[0] + A.shape[1]

    left = solve(row + 1, col, A)
    right = solve(row, col + 1, A)
    best_path = min(right, left)

    return best_path + A[row][col]

想法是，在每个单元格中，您可以向右或向下移动，从该单元格开始的最佳解决方案是从右侧单元格开始的最佳解决方案或从左侧单元格开始的最佳解决方案.取最好的一个加上当前单元格的值，你就得到了从当前单元格开始的解决方案。

虽然可以用递归来解决这个问题，但是对于这种问题动态规划效率更高，感兴趣的可以看看

递归地通过二维二进制数组并计算要通过的“1”的数量

Passing through a 2d binary array recursively and counting the number of "1's" to pass through

python

maze