LC64. Minimum Path Sum

It is very similar to number of paths. But here, we need to change the recurrence relations. We used a 2d array to hold the min number of steps to reach [i][j].
steps[i][j] = min (top or left) + current value.

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        std::vector<std::vector<int>> minSum(m, std::vector<int>(n, 0));
        minSum[0][0] = grid[0][0];
        for (int i = 1; i < n; i ++){
            minSum[0][i] = minSum[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i ++){
            minSum[i][0] = minSum[i - 1][0] + grid[i][0];
        }

        for (int i = 1; i < m; i ++){
            for (int j = 1; j < n; j ++){
                minSum[i][j] = min(minSum[i - 1][j], minSum[i][j - 1]) + grid[i][j];
            }
        }

        return minSum[m - 1][n - 1];

    }

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax