Minimum Path Sum -Runtime error

Revision en2, by mayank_19, 2020-07-29 10:06:55

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.

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)