class Solution:
    '''
    Time Complexity: O(m * n)
    Space Complexity: O(m * n)
    Where, m is number of rows, n is number of columns in the grid.
    '''
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dp(i,j):
            if i >= m or j >= n:
                return 0
            if i == m-1 or j == n-1:
                return 1
            return dp(i+1,j) + dp(i,j+1)
        return dp(0,0)

int[][] visited;
public int uniquePaths(int m, int n) {
    visited = new int[m][n];
    for(int r=0; r<m; r++) {
        visited[r][n-1] = 1;
    }
    for(int c=0; c<n; c++) {
        visited[m-1][c] = 1;
    }
    return getUniquePaths(0, 0, m, n);
}
private int getUniquePaths(int r, int c, int m, int n) {
    if (r >= m | c >= n) {
        return 0;
    }
    if (visited[r][c] > 0) {
        return visited[r][c];
    }
    visited[r][c] = getUniquePaths(r+1, c, m, n) + getUniquePaths(r, c+1, m, n);
    return visited[r][c];
}