Minimum Path Sum -Runtime error

Revision en1, by mayank_19, 2020-07-29 09:59:54

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. source-https://leetcode.com/problems/minimum-path-sum/ ``` class Solution { public: int cal(vector<vector> 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> 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.

Tags #dynamic programing, #runtime, #leetcode, #help, #codefoces, #timelimit, #recursion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English mayank_19 2020-07-29 10:06:55 54 Tiny change: 'own below-~~~~~\n\n~~~~~\' -> 'own below-\n\n~~~~~\'
en1 English mayank_19 2020-07-29 09:59:54 1464 Initial revision (published)