mayank_19's blog

By mayank_19, history, 4 years ago, In English

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.You can only move either down or right at any point in time.

source-https://leetcode.com/problems/minimum-path-sum/

class Solution {
public:
    int cal(vector<vector<int>> v,int n,int m){
        if(m<0 ||n<0)
            return INT_MAX;
        else if(m==0 && n==0)
            return v[0][0];
        else
            return v[n][m]+min(cal(v,n-1,m),cal(v,n,m-1));
        
    }
    int minPathSum(vector<vector<int>>& grid) {
        return cal(grid,grid.size()-1,grid[0].size()-1);   
    }
};

The above solution gives time limit exceeded. Then i tried to memorize it as shown below-


class Solution { public: int memo[10001][10001]; int cal(vector<vector<int>> v,int n,int m){ if(m<0 ||n<0) return INT_MAX; if(memo[n][m]!=-1) return memo[n][m]; else if(m==0 && n==0) return memo[0][0]=v[0][0]; else return memo[n][m]=v[n][m]+min(cal(v,n-1,m),cal(v,n,m-1)); } int minPathSum(vector<vector<int>>& grid) { //memset(memo,-1,sizeof(memo)); return cal(grid,grid.size()-1,grid[0].size()-1); } };

But now it gives runtime error.I am not able to understand what is wrong can someone help me.

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it