Leetcode 64: Minimum Path Sum (recursive + dp)

leetcode_64a.cpp

#include <iostream>
#include <vector>

using namespace std;

int count(const vector<vector<int>>& grid, int rows, int cols, int r, int c, vector<vector<int>>& dp) {
    if (r == rows || c == cols) return INT_MAX;
    if (r == rows-1 && c == cols-1) return grid[r][c];
    if (dp[r][c] != -1) return dp[r][c];
    dp[r][c] = min(count(grid,rows,cols,r+1,c,dp),count(grid,rows,cols,r,c+1,dp))+grid[r][c];
    return dp[r][c];
}

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, -1));
    return count(grid, rows, cols, 0, 0, dp);
}

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