C++ DP and 22ms


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

    I solved it using DP. It is very simple approach.. It follows optimal substructure. We just have to check which previous value + current value gives us minimum path.


Log in to reply
 

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