Data Structures & Algorithms in Java – Dynamic Programming – Unique Paths

Problem:

Given a 2 dimensional matrix size m * n , find the number of unique ways to reach the bottom right of the matrix from the top left of the matrix (first cell) if you can move only right or down a step at a time .

That is from input[0][0] to input[m-1][n-1]

For example , for the input :

m = 3 , n = 2

The output is 3:

  1. Right -> Down -> Down
  2. Down -> Down -> Right
  3. Down -> Right -> Down

Try out the solution here:

https://leetcode.com/problems/unique-paths/

Advertisements

Solution:

Hint:

You either move along the column or along the row incrementally. So ,

Number of ways to reach any position in the matrix = Number of ways to reach the previous row current column cell + Number of ways to reach the current row previous column cell

ie) Ways[i][j] = Ways [i-1][j] + Ways[i][j-1]

Where i represents the current row and j represents the current column.

We can solve the above problem recursively by setting the base conditions:

  • If row or column value is negative , return 0
  • If row or column value is 0 , return 1. It means there is only one row or one column. We return 1 because if there is only one row or column , then you can move only once in one direction to reach the destination.

Once the base conditions are set , recursively compute the number of ways to reach previous row and current column position . Also recursively compute the number of ways to reach previous column and current row position. Add them both and return.

Here is the code:

Recursion Code:

class Solution {
    public int uniquePaths(int m, int n) {
        
        return recursion(m-1,n-1);
    }
    
    
    public int  recursion(int right,int down){
              if(right < 0 || down < 0){ 
                   return 0;
                  }
                
        if( right ==0 || down ==0) return 1;
        
         return recursion(right - 1, down)+ recursion(right , down -1);
    }
}

The time complexity is exponential in the above case because of the recursive calls. We can avoid repeated recursive calls by storing the result of the recursive calls in an array . This technique is known as Memoization. So you return the result from the array if already present and make the recursive call only if not present.

Memoization Code:

Code is very similar to the above except for storing result of the sub problems in an array and returning results from it.

class Solution {
    public int uniquePaths(int m, int n) {
        
        int[][] dp = new int[m][n];
        
        return recursion(m-1,n-1,dp);
    }
    
    
    public int  recursion(int right,int down,int[][] dp){
        
        if(dp[right][down] !=0){
            
            return dp[right][down];
        }
     if(right < 0 || down < 0){ 
         return 0;
     }
        
              
        if( right ==0 || down ==0) return 1;
      
         int result =  recursion(right - 1, down,dp)+ recursion(right , down -1,dp);
        dp[right][down] = result;
        
        return result;
}
}
Advertisements

You can further avoid the recursion calls altogether using bottom up dynamic programming this way:

Bottom Up Dynamic Programming:

ALGORITHM:

STEP 1: Initialize an output array to store the results of number of unique paths at each index of the matrix

STEP 2: For the first row and first column values initialize the output as 1 as there is only one way to reach the end of the matrix if there is only one row or one column.

STEP 3: For all other positions , calculate the output using formula:

Number of unique paths to a position in the matrix = Number of unique ways till the previous row , current column + Number of unique ways till the previous column, current row

STEP 4: Return the value of the last element which represents the bottom right element.

Code:

class Solution {
    public int uniquePaths(int m, int n) {
        
        
        int[][] dp = new int[m][n];
        
        for(int i=0;i<m;i++){
            
            dp[i][0] = 1;
        }
        
        for(int j=0;j<n;j++){
            
            dp[0][j] = 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];
    }
}

Time complexity is O(m * n ) where m and n are the dimensions of the matrix and space complexity is also O( m * n) as we use a two dimensional array to store the results .

We can do one more optimization here.

If you notice the code :

                dp[i][j] = dp[i-1][j]+dp[i][j-1];

The result above represents the sum of the value in the previous row for the current column and the value in the current row previous column.

It could be replaced by a one dimensional array and using the below code:

                dp[j] = dp[j]+dp[j-1];

In the above sum , the first operand dp[j] represents the value of the current column in the previous row and the second operand dp[j-1] represents the value of the previous column in the current row. Adding both gives the new dp[j] which represents the value of the current row and current column.

Since both the sums return the same value, so we can use the later and minimize the space used.

Advertisements

Here is the refactored code:

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

Time complexity remains the same O(m * n) whereas space complexity is reduced to O(n)

Let’s understand this visually using the below example :

Let’s take the 3 * 2 matrix again.

Let’s first initialize all the values to 1:

Notice that dp[0] represents the first column value for all the rows.

dp[1] represents the second column values for all the rows.

Now let’s use the formula

 dp[j] = dp[j]+ dp[j-1]

Lets use it for j = 1 and i = 1 (second row and second column)

We are now going to calculate dp[1] for the second row.

As we have already learned the formula

Number of unique paths at a position = Number of unique paths at the previous row current column + Number of unique paths at the current previous column

dp[1] = Number of unique paths at column 1 , row 0 + Number of unique paths at column 0 , row 1. From the above diagram you can easily add both and find the solution as 2 (1 + 1)

Let us use the formula to find the same:

Number of unique paths at column 1 row 0 dp[1] is already initialized to 1

Number of unique paths at column 0 row 1 dp[0] is also already initialized to 1.

So ,

dp[1] (for current row) = dp [1] (for previous row) + dp[0] = 1 + 1 = 2

Now lets take i = 2 , j = 1

Again use the formula

dp[1] (for row 2) = dp[1] (for row 1 already calculated in the previous step) + dp[0] (for row 2)

dp[1] = 2 + 1 = 3

Return the last value 3.

That’s it!

3 thoughts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s