Recursive DP 9ms C++ Solution


  • 0
    A
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
           vector<vector<int> > sums(grid.size()+1, vector<int>(grid[0].size()+1, INT_MAX)); 
            return minPathSumHelper(grid,sums, 0,0);
        }
        int minPathSumHelper(vector <vector<int>> & grid, vector <vector<int>> & sums, int i, int j){
            int m = grid.size()-1,  n = grid[0].size()-1;
            if( i ==m && j == n ){
                return grid[m][n];
            }
            if(i < m && sums[i+1][j] == INT_MAX )
                sums[i+1][j] = minPathSumHelper(grid, sums, i+1, j);
            if(j < n && sums[i][j+1] == INT_MAX)
                sums[i][j+1] = minPathSumHelper(grid,sums, i, j+1);
            return grid[i][j]+ min( sums[i+1][j],sums[i][j+1] );
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.