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!
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$).
.... .... ....
Number of paths = 10
..#. #.#. ....
Number of paths = 1
...# .#.. ....
Number of paths = 3
Once you are confidant of your solution, take the quiz! It will provide you with some grids to run your code on.
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).
The solution for this assignment is included at the end of the quiz.