Leetcode 64: Minimum Path Sum (iterative dp)

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

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

    for (int r=1; r<rows; ++r) {
        for (int c=1; c<cols; ++c)
            dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + grid[r][c];
    }
    
    return dp[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;
}