minimum cost path in matrix

Question

Question -

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.

It shows incorrect output.

Example -

1 2
1 1

It gives the output as 2. where as the answer is 3.

Thanks.

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

I am assuming you meant you are getting the "incorrect output"? Anyways, your question is not clear because you have not stated what the problem is and what the expected output is and all you have posted is your solution to...something — smac89, Sep 07 '16 at 05:08

D-Von · Accepted Answer · 2016-09-07T16:46:56.887

2

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

edited Sep 07 '16 at 16:46

answered Sep 07 '16 at 05:39

D-Von

416
2
5

No its reaching 1,1, then how can change the code? I am returning 0 oly when n > len – Ryo Sep 07 '16 at 16:24
I recommend that you adjust your what-to-return logic. I have edited my answer. – D-Von Sep 07 '16 at 16:41

minimum cost path in matrix

1 Answers1

Linked