矩阵中的最小成本路径 [英] minimum cost path in matrix

问题描述

问题-

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

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

注意：您只能在任何时间点向下或向右移动

Note: You can only move either down or right at any point in time

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

I know this is a common question and most of you guys would know the question as well as its dynamic programming. I am trying the recursive code here but I am getting the correct output. what is missing in my recursive code? I don't want the iterative or dynamic programming approach. I am trying to build on my own.

显示错误的输出。

示例-

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，然后是从网格底部掉落的成功。我建议您调整返回收益的逻辑，使其看起来像这样：

I don't think it's correct to return 0 when you fall off the edge of the grid. That makes it look like you've succeeded. So I think the 2 that you are erroneously reporting is the 1 in upper left plus the 1 in lower left, followed by a "successful" falling off the bottom of the grid. I recommend you adjust your what-to-return logic so it looks like this:

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

这篇关于矩阵中的最小成本路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！