CLEAN CODE | DYNAMIC PROGRAMMING | RUBY | TOTAL NUMBER OF PATHS

By: Saurav

2018-03-15 03:17:00 UTC

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Leetcode

Below is a 3 x 7 grid. How many possible unique paths are there?

Note: Images are from Leetcode.

Robot maze

This is a simple dynamic problem if you can visualize it.

In Dynamic programming:
First, we try to guess the solution.
Here the problem is how many ways is it possible to reach a square. A total of 8 ways is our guess.
Out of those 8 ways, we smartly choose only two, as the movement is allowed in only two directions.
Then we take the solutions from solving the two subproblems (ways to reach those square) and combine them according to an aggregation function. In this case, the function is an addition.

For the subproblem of finding the path in the first row and column, we know its one 1.
We then memoize the problem and build next solution based on the previous ones.

Let's see it in action

def unique_paths(m, n)
    
    #Here dynamic programming is taking the two subproblems and joining them with an addition operation.
    return 0 if m < 1 or n < 0
    return 1 if n < 1 or m < 1
    
   #We fill the array with 1 because the subproblem of finding a path in first row and column will give us 1.
    arr = Array.new(m){Array.new(n,1)}
    
    (1..m-1).each do |i|
        (1..n-1).each do |j|
            arr[i][j] = arr[i-1][j] + arr[i][j-1]
        end
    end
    
    return arr[-1][-1]
end

A better in-pace strategy can be to use the same array and change the code a lil:

def unique_paths_with_obstacles(obstacle_grid)
    m = obstacle_grid.length
    n = obstacle_grid[0].length
    return 0 if obstacle_grid.length == 0 
    
    #arr = Array.new(m){Array.new(n,0)}    
    
    (0..m-1).each do |i|
        (0..n-1).each do |j|
            if i == 0 and j == 0 
               obstacle_grid[i][j] = 1
            elsif i == 0 
               obstacle_grid[i][j] =  obstacle_grid[i][j-1]
            elsif j == 0 
               obstacle_grid[i][j] =  obstacle_grid[i-1][j]
            else
                 obstacle_grid[i][j] =  obstacle_grid[i][j-1] +  obstacle_grid[i-1][j]
            end
        end
    end
    
    return  obstacle_grid[-1][-1]
end

The same question can have an extension like this:

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

.Leetcode

Everything remains the same except one check. if obstacle_grid[i][j] == 1 -> obstacle_grid[i][j] = 0 and the obstacle will betaken care of

def unique_paths_with_obstacles(obstacle_grid)
    m = obstacle_grid.length
    n = obstacle_grid[0].length
    return 0 if obstacle_grid.length == 0 
    
    #arr = Array.new(m){Array.new(n,0)}    
    
    (0..m-1).each do |i|
        (0..n-1).each do |j|
            if obstacle_grid[i][j] == 1
                 obstacle_grid[i][j] = 0
            elsif i == 0 and j == 0 
               obstacle_grid[i][j] = 1
            elsif i == 0 
               obstacle_grid[i][j] =  obstacle_grid[i][j-1]
            elsif j == 0 
               obstacle_grid[i][j] =  obstacle_grid[i-1][j]
            else
                 obstacle_grid[i][j] =  obstacle_grid[i][j-1] +  obstacle_grid[i-1][j]
            end
        end
    end
    
    return  obstacle_grid[-1][-1]
end


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)