**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?

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

Note: Images are from Leetcode.

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

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

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.

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

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 :)