0
votes

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.

Eg: [1,3,1],[1,5,1],[4,2,1]]

Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.

My solution using recursion but it is wrong, please help me correct it and explain what am I missing.

import math

def minPath(grid,n,m,a,b):
    if n>a or m>b:
        return math.inf
    grid[n][m] += min(minPath(grid,n+1,m,a,b),minPath(grid,n,m+1,a,b))
    return grid[n][m]

def minPathSum(grid):
    m = len(grid) - 1
    n = len(grid[0]) - 1
    a = m-1
    b= n-1
    minPath(grid,0,0,a,b)
    return grid[a][b]

print(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
3
remove double decrementing by 1 for borders and recheck if-condition (n>b,m>a) - MBo
@MBo can you elaborate please - Utkarsh Prakash

3 Answers

0
votes

Remove double decrementing by 1 for borders and change if-condition

 if n>b or m>a:
 ....
 a = m    //2 for 3x3 map
 b = n

Possible main issue: if your grid is modified globally, you'll get wrong solution (perhaps your implementation makes local copy at every recursion call)

0
votes

you forget to add the successful condition, ie. if the recursive solution approach the final grid, then return the grid value

if n==a and m==b:
  return grid[n][m]

So the final solution should look like this:

import math

def minPath(grid,n,m,a,b):
    if n>a or m>b:
        return math.inf
    if n==a and m==b:
        return grid[n][m]
    return grid[n][m] + min(minPath(grid,n+1,m,a,b),minPath(grid,n,m+1,a,b))

def minPathSum(grid):
    m = len(grid) - 1
    n = len(grid[0]) - 1
    a = m-1
    b= n-1
    minPath(grid,0,0,a,b)
    return grid[a][b]

print(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
0
votes
#include<bits/stdc++.h>
using namespace std;
int minimumCostPath(vector<vector<int>> &path, int i, int j){
    int m = path.size() - 1;
    int n = path[0].size() - 1;
    if(i > m || j > n) return INT_MAX;
    else if(i == m && j == n) return path[i][j];

    int x = minimumCostPath(path, i + 1, j);
    int z = minimumCostPath(path, i , j + 1);



    int smallOutput = min(z, x) + path[i][j];

    return smallOutput;

  }
int main(){

    vector<vector<int>> path = { { 1, 2, 3 },{ 4, 8, 2 },{ 1, 5, 3 } };
    cout << minimumCostPath(path, 0, 0);

    return 0;
}