Leetcode 64: Minimum Path Sum (iterative dp, const aux space)

leetcode_64d.cpp

#include <iostream>
#include <vector>

using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int rows = grid.size(); 
    if (rows == 0) return 0;
    int cols = grid[0].size(); 
    if (cols == 0) return 0;

    for (int c=1; c<cols; ++c) 
        grid[0][c] = grid[0][c-1] + grid[0][c];
    for (int r=1; r<rows; ++r) 
        grid[r][0] = grid[r-1][0] + grid[r][0];

    for (int r=1; r<rows; ++r) {
        for (int c=1; c<cols; ++c)
            grid[r][c] = min(grid[r-1][c], grid[r][c-1]) + grid[r][c];
    }
    
    return grid[rows-1][cols-1];
}

int main() {
    vector<vector<int>> grid {{1,3,1},{1,5,1},{4,2,1}};
    cout << minPathSum(grid) << "\n";
    return 0;
}