Recursion

New York Paths

Dynamic Programming

You're driving in New York city, represented as the grid below. You start at the top-left corner of the city, and can either drive South or East. You need to get to the bottom-right corner of the city to win a prize.

Assume the city is n x m blocks large. Return the number of ways you can get to the bottom-right corner.

Example:

=> returns 3\notag \texttt{\large => returns 3}

Explanation: There are 3 unique paths that lead to the coin.

First Few Test Cases:

1. Recursion

To solve this problem, we want to find the number of paths that lead into the bottom right corner. We can write a recursion that computes the number of paths that lead into a particular square.

The the number of ways get to any square is equal to the number of ways to get to that square from the top, plus the number of ways to get to it from the left.

2. Base case

The recursion will keep calling itself on smaller m's and n's, until it gets to a square that's out of bounds. You need a base case for when this happens. There are no ways for your car to get out of bounds:

You also need a base case to indicate that you start at the top left corner.

3. Code

You can code this up using regular recursion, but it's very slow.

To code this up, you can use "Tabulation". The function call numPaths(m, n) depends on numPaths of smaller m and n, so we can compute the smallest m and n first and the biggest ones last. Here's the code:

Time Complexity O(nm)O(n \cdot m)

Space Complexity O(nm)O(n \cdot m)

You don't have to know this for an interview, but you can solve this problem with only math. The car always steps right n-1\texttt{n-1} times, and down m-1\texttt{m-1} times, giving m-n-2\texttt{m-n-2} steps total. Out of all these steps, we want to choose m-1\texttt{m-1} of them to be down steps, and the rest of them to be right steps (or we could choose the other way, it doesn't matter). You can write this with math as:

numMatrixPaths(m, n) = (m-n-2)!(n-1)!    (m-1)!\notag \texttt{numMatrixPaths(m, n) = } \frac{\texttt{(m-n-2)!}}{\texttt{(n-1)!} \;\; \texttt{(m-1)!}}

Here's how you can code this up.

Time Complexity O(1)O(1)

Space Complexity O(1)O(1)

Mark as Completed:
Submits:
numMatrixPaths
Test your code to get an output here!
numMatrixPaths(
)
Test your code to get an output here!