# Hands-on: Paths in a Grid (with progressive 'hint-by-hint' solution)

July 03, 2018

Enough of the tiling problems. Time for some 2D dynamic programming. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

# Problem Statement

You are given a grid with $n$ rows and $m$ columns. Some of the grid locations are blocked, and cannot be entered. Find the number of paths from the top-left corner of the grid to the bottom right corner.

Your solution should have run-time O($nm$).

# Examples

**Example 1:**

```
....
....
....
```

Number of paths = 10

**Example 2:**

```
..#.
#.#.
....
```

Number of paths = 1

**Example 3:**

```
...#
.#..
....
```

Number of paths = 3

# Submitting your solution

Once you are confidant of your solution, take the quiz! It will provide you with some grids to run your code on.

# Progressive ‘hint-by-hint’ solution

Only look at the hints if you can’t solve the problem for **at-least 20-minutes**. Read **only one hint** that you could not figure out on your own. Then spend **at-least 20-minutes** trying to solve the problem again.

Hint 1 (dp state):

count(i, j) = number of paths from (0, 0) to (i, j)

Hint 2 (recursion):

You can either come from top, or from the left. Hence, if square (i, j) is not blocked, then count(i, j) = count(i-1, j) + count(i, j-1).

# Full solution

The solution for this assignment is included at the end of the quiz.