Grid unique path

#dp #matrix #array #dsa

TC: O(n*m)
SC: O(n*m) for dp array, and O(n+m) for recursive stack space

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for(int d[] : dp) Arrays.fill(d,-1);
        return paths(0,0,m,n,dp);
    }
    public int paths(int i ,int j ,int m, int n,int dp[][]){
        //base case
        if(i==m || j==n) return 0;// path ended not found
        if(i == m-1 && j ==n-1) return 1;//one path found 
        if(dp[i][j]!=-1) return dp[i][j];

        int right = paths(i,j+1,m,n,dp);
        int down = paths(i+1,j,m,n,dp);

        return dp[i][j] = right+down;


    }
}