Pascal’s Dynamic Path

There’s a dynamic programming interview question which asks how many possible paths exist from one corner of a grid to the opposite corner if one can only move to the right or down. A naive approach is to attempt a modified depth-first search, but the most straightforward solution is to realize that each grid square can contain a number representing the ways to reach the square above it and the square to the left of it. The topmost row and leftmost column remain unchanged since any space outside of the grid adds nothing to the total.

By employing this method, the number of possible paths from the top-left grid space to any arbitrary grid space can be calculated in O(M * N) time and M * N space complexity. It works even with “landmine” grid spaces the coder must exclude. Something interesting, however, happens when the grid is rotated by 45 degrees and filled in with discrete values.

This rotation demonstrates that there is a direct connection between the grid-path problem outlined above and Pascal’s Triangle. Given a grid dimension in the form of M * N, is it possible to compute the equivalent position of the destination grid space?

It turns out that any particular position in Pascal’s Triangle can be computed by “n choose k” which is computed by:

n! / (k! * (n - k)!)

Let’s imagine a grid 3 units wide and 6 units tall. To convert these dimensions to a position on Pascal’s Triangle, we subtract 1 from each dimension yielding 2 and 5. We add the two together to obtain 7 which is our n and select the lesser, 2, to be our k.

n! / (k! * (n - k)!)
7! / (2! * (7 - 2)!)
7! / (2! * 5!)
5040 / (2 * 120)
21

Let’s try 5 units wide and 4 units tall. Reduce each dimension by 1 to obtain 4 and 3. Add them together to obtain 7 which is our n. The lesser of the two, 3, is our k.

n! / (k! * (n - k)!)
7! / (3! * (7 - 3)!)
7! / (3! * 4!)
5040 / (6 * 24)
35

Finally, let’s try 9 units by 9 units. That becomes 8 and 8 with n being 16 and k being 8.

n! / (k! * (n - k)!)
16! / (8! * 8!)
12870

In C++, the tgamma() function may prove to be useful when implementing this algorithm. There is a tradeoff, however, that the size of the factorials used in the algorithm grows much faster than any value in Pascal’s Triangle. This introduces the possibly of overflow and increased total time due to working with very wide storage variables. However, this algorithm will operate, where successful, in constant O(1) time and stack space complexity if coded properly. Naive implementations for factorial calculation grow in linear time and linear stack space with the value of the factorial i.e. 7! may require two more stack frames than 5!