Homework 7

Download the corresponding ipynb file here: hw-7.ipynb.

Dynamic Programming

The solutions are incorporated from Nammin Woo.

Exercise 1 (10 Points) Let us represent a rectangular maze by an m\times n matrix. Suppose there is a mouse in the maze. It starts from the entrance at entry (0,0). Each time the mouse can either move to the right or go down. The objective is to the exit, located at entry (m-1, n-1). Design an algorithm to return the number of ways the mouse can get out of a maze of size m\times n. Your algorithm must have

• \mathcal{O}(m\times n) time-complexity
• \mathcal{O}(m\times n) space-complexity

You may either given a pseudocode or Python implementation.

Exercise 2 (🏅 Bonus) Can you make the space complexity better than \mathcal{O}(m\times n)?