The Unique Paths with Obstacles problem using Dynamic Programming

In this article, we will cover a famous dynamic programming question, "Unique paths with Obstacles".
So Let's Start.

What is Unique Paths with Obstacles Problem?

Consider a robot/person that has to reach from a starting point to a final location in a 2D grid with m rows and n columns
The person to start with is on the top left position (0,0) and it has to reach the last cell, the bottom right corner (m-1, n-1)
The path also has some obstacles on which our robot can not step upon. Denoted by 1. The safe cells are denoted by 0.
Our person can only move DOWN OR RIGHT AT ANY POINT IN TIME, It has only these two choice
Now it is sure that the guy can reach the end, but how many unique paths are there? Paths which lead to the end and also don't contain any obstacles. This is what we need to compute!

Some examples:

Example 1:
Input:
[[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
In the above example, there is on obstacle in the middle of the grid, we can follow any one of these 2 paths, these are the only unique paths, i.e:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Initial takes on the question:

• We need to reach the bottom right cell of the grid step by step
• We have to make a choice at every step we take, the choices are: Go right or Go down!
• There are some places in the path on which we can not put our step
• We need to tell that in how many unique (distinct) ways are there to reach the end point!

Now that we have pretty much understood what the question wants we will now understand how to approach it in a step by step manner

Let's try to break the problem down a bit. Just to make things easier to understand and see if we can form some relation!
So to reach a given cell, I can either come from the cell right above me or the cell that is right to the left of me, but if I see an obstacle above me or on my right, then I can not come from there.
Looking a the diagram it is pretty clear that to reach a cell (i,j), I can either come from cell (i-1, j) or from the cell (i, j-1).
These are all the possibilities! Hence the answer for this cell is nothing but the sum of the possibilities on these two cells! Simple as that!
Note that for a cell having obstacle say above it, but a clear path to the left of it, it's only possibility is from the left.

Now lets go through the example properly to understand how the DP concept will walk into picture!
Say that we have the following example at hand
Remember at each point we can either go right or go down, so lets try to understand it now! Let's look at the possibilities:

• Notice how we will make use of pre-computed results
• To reach any point in the first row, we can only go right always, hence to reach any cell in this row there is only and only 1 way! But the moment you find an obstacle! You can't reach it and also anything next to it in that row!
• Similarly, To reach any point in the first column, we can only go down always, hence to reach any cell in this column there is only and only 1 way! But the moment you find an obstacle! You can't reach it and also anything next to it in that column!
• Now our real thinking starts, think about the cell at (1,1) we can reach it either from (0,1) or from (1,0) i.e. from the Top or from the Left. Hence we will write here a 1+1 = 2.
• Look one step right now at cell (1,2), I can come here from top (0,2) or from the left (1,1). Now we have a big advantage here! We do not need to recompute the value for the cell (1,1) we have stored it already! Hence in this cell we can fill the sum of values from (0,3) and (1,1) = 1 + 2 = 3
• But if anywhere in the above mentioned process, there is a cell on which I can not step on, don't go forward into making any calculations, make it zero! Simply saying mark it such a cell that can not contribute in any way to the number of ways of generating the paths!

And similarly, we can fill the remaining values, but wait a minute... did you notice some pattern?
To compute value at (1,1) we used--> (1,0) and (0,1)
To compute value at (1,2) we used--> (1,1) and (0,2)
.
.
.
To compute value at (2,6) we will use-->(2,5) and (1,6)

So do you see it? [i,j] = [i-1,j] + [i, j-1] is the relation we wanted, the relation we were using!

Now simply following the steps discussed above we can write our code, we will be using a 2D array (dp) to store the computations, so that we can use them later!