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

leetcode_64c.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;
    vector<int> dp(cols, 0);

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

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

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