DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Grid unique path

Problem

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;


    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay