Java Dynamic Programming solution with detailed explanation, only need a 1-dimensional array


  • 3
    Y

    The idea is like this:
    Since we only need to know N[m-1][n-1] for a m*n grid, it is a waste of space to keep the whole 2-dimensional array. And we also know that N[i][j] = N[i-1][j] + N[i][j-1], so if we use only a one dimensional array and let N[i] = N[i] + N[i-1]. i.e. the N[i] at the left side of the equation and N[i-1] actually stores the number of path at the next row in a 2-dimensional array, and N[i] at the right side of the equation stores the number of paths at the current row in a 2-dimensional array. So in general, every element on the left side of N[i] in the 1 dimensional array is actually the value at the next row if in a 2-dimensional array.
    By filling the array from left to right, we will never rewrite a value before we making use of it.

    public class Solution {
    public int uniquePaths(int m, int n) {
        /*
        Dynamic Programming
        Bottom-up approach
        If we use Num[n] to denote the number of paths and we fill this form from left to right, we will never rewrite a value before we make use of it.
        O(mn) time and O(n) space
        */
        if (m == 0 || n == 0){
            return 0;
        }
        
        int[] Num = new int[n];
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j++){
                if (i == 0 || j == 0){
                    Num[j] = 1;
                }
                
                else {
                    Num[j] += Num[j-1];
                }
            }
        }
        
        return Num[n-1];
    }
    

    }


  • 1

    That's amazing!!!!


  • 0
    R

    said in Java Dynamic Programming solution with detailed explanation, only need a 1-dimensional array:

    N[i-1] actually stores the number of path at the next row in a 2-dimensional array

    I found this very confusing, or at least I don't understand the term next row here. By next row, did you mean last row? last row means you have already run through that row. is this understanding correct? next row means you have NOT run through that row yet.


  • 0
    Y

    @rcholic Hi, by next row, I mean when we are calculating N[i], N[i-1] actually stored the value of the next row compare to N[i]'s current value. When we finish calculating N[i] += N[i-1], N[i] now becomes the number of path for next row again, compared with every thing on the right side of N[i].


  • 0
    R

    @YaokaiYang , What you just said further confirms that N[i-1] refers to the last row, not the next row.


Log in to reply
 

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