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;
}
}
Top comments (0)