10 lines recursive with O(1) space O(n) time solution.


  • 0
    F

    Here is the code:

        int minPathSum(vector<vector<int>> & grid, int r, int c) {
            if (r >= grid.size() || c >= grid[0].size()) return INT_MAX;
            if (grid[r][c] >= 0) {
                int v = min(minPathSum(grid, r, c+1), minPathSum(grid, r+1, c));
                grid[r][c] = -(grid[r][c] + ((v == INT_MAX) ? 0 : v));
            }
            return -grid[r][c];
        }
        int minPathSum(vector<vector<int>>& grid) {
            if (grid.empty() || grid[0].empty()) return 0;
            return minPathSum(grid, 0, 0);
        }
    

    It is actually the same idea as following recursive plus memorization solution, just reuse grid itself as cache. Since grid contains only non-negative numbers, we change it to -minPathSum after we figure it out.

        int minPathSum(vector<vector<int>> & grid, int r, int c, vector<vector<int>> & cache) {
            if (r == grid.size() - 1 && c == grid[0].size() - 1) return grid[r][c];
            if (cache[r][c] != -1) return cache[r][c];
            int v = INT_MAX;
            if (r < grid.size() - 1) v = min(v, minPathSum(grid, r+1, c, cache));
            if (c < grid[0].size() - 1) v = min(v, minPathSum(grid, r, c+1, cache));
            cache[r][c] = grid[r][c] + v;
            return grid[r][c] + v;
            
        }
        int minPathSum(vector<vector<int>>& grid) {
            if (grid.empty() || grid[0].empty()) return 0;
            vector<vector<int>> cache(grid.size(), vector<int>(grid[0].size(), -1));
            return minPathSum(grid, 0, 0, cache);
        }
    

    And we can re-write the code in DP iterative way use same idea:

        int minPathSum(vector<vector<int> > &grid) {
            if (grid.empty() || grid[0].empty()) return 0;
            for (int i = 0; i < grid.size(); i++) {
                for (int j = 0; j < grid[0].size(); j++) {
                    if (j > 0 && i > 0) {
                        grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
                    } else if (j > 0) {
                        grid[i][j] += grid[i][j-1];
                    } else if (i > 0) {
                        grid[i][j] += grid[i-1][j];
                    }
                }
            }
            return grid.back().back();
        }
    

Log in to reply
 

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