Java based Approach (Dynamic Programming)


  • 0
    T

    This technique uses two one dimensional arrays, prev and curr to store state about previous and current rows. At each step it adds the ways from where it can be reached.

    int prev[] = new int[n];
    Arrays.fill(prev, 1);
    int curr[];
    for(int i = 1; i < m; i++) {
         curr = new int[n];
         Arrays.fill(curr, 1);
         for(int j = 1; j < n; j++) {
               curr[j] = curr[j-1] + prev[j];
         }
         prev = curr;
    }
    return prev[n-1];
    

    This technique uses 2D array to stores the ways it can reach that block. Any comments appreciated.

            int dp[][] = new int[m][n];
            for(int j = 0; j < n; j++) {
                dp[0][j] = 1;
            }
            for(int i = 0; i < m; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i < m; i++) {
                 for(int j = 1; j < n; j++) {
                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
                 }
            }
            return dp[m-1][n-1];
    

Log in to reply
 

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