矩阵中的最小成本路径

  • Z时代
  • 2024-01-10
  • 分类：问答

题 -

给定用非负数填充的amxn网格，请找到从左上到右下的路径，该路径将沿其路径的所有数字的总和最小化。

注意：您只能在任何时间点上下移动

我知道这是一个常见问题，并且你们大多数人都会知道该问题及其动态编程。我在这里尝试递归代码，但得到正确的输出。我的递归代码中缺少什么？我不希望使用迭代或动态编程方法。我正在尝试自己建立。

显示错误的输出。

范例-

1 2
1 1

输出为2.，答案为3。

谢谢。

def minPathSum(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    def helper(i,j,grid,dp):
        if i >= len(grid) or j >= len(grid[0]):
            return 0
        print grid[i][j]
        return grid[i][j]+min(helper(i+1,j,grid,dp),helper(i,j+1,grid,dp))
    dp = [[0] * len(grid[0]) for i in range(len(grid))]
    val = helper(0,0,grid,dp)
    print dp
    return val

回答：

我认为从网格边缘掉下来返回0并不正确。这样看来您已经成功了。因此，我认为您错误地报告的2是左上角的1​​加左下角的1，然后是“成功”从网格底部掉落的情况。我建议您调整返回收益的逻辑，使其看起来像这样：

if at right or bottom edge:
  there is only one direction to go, so
  return the result of going in that direction
else you do have options, so
  return the minimum of the two choices, like you do now

以上是 矩阵中的最小成本路径 的全部内容， 来源链接： utcz.com/qa/408474.html

回到顶部