Leetcode 63: Unique Paths II (recursive + dp)

leetcode_63a.cpp

#include <iostream>
#include <vector>

using namespace std;

int count(const vector<vector<int>>& obs, int rows, int cols, int r, int c, vector<vector<int>>& dp) {
    if (r == rows || c == cols) return 0;
    if (obs[r][c] == 1) return 0;
    if (r == rows-1 && c == cols-1) return 1;
    if (dp[r][c] != -1) return dp[r][c];

    dp[r][c] = count(obs,rows,cols,r+1,c,dp) + count(obs,rows,cols,r,c+1,dp);
    return dp[r][c];
}

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int rows = obstacleGrid.size();
    if (rows == 0) return 0;
    int cols = obstacleGrid[0].size();
    if (cols == 0) return 0;
    vector<vector<int>> dp(rows, vector<int>(cols, -1));
    return count(obstacleGrid, rows, cols, 0, 0, dp);
}

int main() {
    vector<vector<int>> obs{{0,0,0},{0,1,0},{0,0,0}}; //{{1}};
    cout << uniquePathsWithObstacles(obs) << "\n";
    return 0;
}