Leetcode 62: Unique Paths - recursive DP

leetcode_62b.cpp

#include <iostream>
#include <vector>

using namespace std;

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

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(n, vector<int>(m, -1));
    return count(n, m, 0, 0, dp);
}

int main() {
    int m = 7, n = 3;
    cout << uniquePaths(m, n) << "\n";
    return 0;
}