9ms DP solution in C++


  • 0
    V
    int minPathSum(vector<vector<int>>& grid) {
            if(grid.empty())
                return 0;
            
            vector<vector<int>> minPath(grid.size(), vector<int>(grid[0].size(), INT_MAX));
            
            minPath[0][0] = grid[0][0];
            
            for(int i = 0; i < grid.size(); ++i) {
                for(int j = 0; j < grid[0].size(); ++j) {
                    int current = INT_MAX;
                    if(i > 0)
                        current = min(current, minPath[i - 1][j] + grid[i][j]);
                    if(j > 0)
                        current = min(current, minPath[i][j - 1] + grid[i][j]);
                    
                    minPath[i][j] = min(minPath[i][j], current);
                }
            }
            return minPath[minPath.size() - 1][minPath[0].size() - 1];
        }
    

Log in to reply
 

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