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.