Detail explanation in Java


  • 0
    L

    The approach to solve these kind of problems is to go to the penultimate cells and figure out how many steps will it take from there to reach to the last one. This models a recursive solution like below:

    T(m,n) = T(m-1,n) + T(m,n-1).

    However, the recursive solution will give you TLE as expected. I tried the memoization approach and that TLEed as well. Here is the top-down DP with memoization:

    private int helper_top_down(int m, int n,int[][] dp) 
        {
            if(m==1 || n==1) {
                return 1;
            }
            if(m<=0 || n<=0) {
                return 0;
            }
            
            int path = 0;
            //check if right path is possible
            //to reach here.
            if(n>1) {
                if(dp[m][n-1]==-1) {
                    dp[m][n-1] = uniquePaths(m,n-1);
                }
                path = dp[m][n-1];
            }
            if(m>0) {
                if(dp[m-1][n]==-1) {
                    dp[m-1][n] = uniquePaths(m-1,n);
                }
                path += dp[m-1][n];
            }
            return path;
            
        }
    

    Now, I fell back to the regular bottoms-up dp as below. As expected, it got accepted.

    public int uniquePaths(int m, int n) {
            int[][] dp = new int[m+1][n+1];
            //bottoms-up dp.
            for(int i=0;i<=m;i++) {
                for(int j=0;j<=n;j++) {
                    dp[0][j]=0;
                    dp[i][0]=0;
                    dp[1][j]=1;
                    dp[i][1]=1;
                }
            }
            int path = 0;
            for(int i=2;i<=m;i++) {
                for(int j=2;j<=n;j++) {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
            
            return dp[m][n];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.