Finding all paths down stairs?

Question

I was given the following problem in an interview:

Given a staircase with N steps, you can go up with 1 or 2 steps each time. Output all possible way you go from bottom to top.

For example:

N = 3

Output :
1 1 1
1 2
2 1

When interviewing, I just said to use dynamic programming.

S(n) = S(n-1) +1 or S(n) = S(n-1) +2

However, during the interview, I didn't write very good code for this. How would you code up a solution to this problem?

Thanks indeed!

Answer 1

I won't write the code for you (since it's a great exercise), but this is a classic dynamic programming problem. You're on the right track with the recurrence; it's true that

S(0) = 1

Since if you're at the bottom of the stairs there's exactly one way to do this. We also have that

S(1) = 1

Because if you're one step high, your only option is to take a single step down, at which point you're at the bottom.

From there, the recurrence for the number of solutions is easy to find. If you think about it, any sequence of steps you take either ends with taking one small step as your last step or one large step as your last step. In the first case, each of the S(n - 1) solutions for n - 1 stairs can be extended into a solution by taking one more step, while in the second case each of the S(n - 2) solutions to the n - 2 stairs case can be extended into a solution by taking two steps. This gives the recurrence

S(n) = S(n - 2) + S(n - 1)

Notice that to evaluate S(n), you only need access to S(n - 2) and S(n - 1). This means that you could solve this with dynamic programming using the following logic:

1. Create an array S with n + 1 elements in it, indexed by 0, 1, 2, ..., n.
2. Set S[0] = S[1] = 1
3. For i from 2 to n, inclusive, set S[i] = S[i - 1] + S[i - 2].
4. Return S[n].

The runtime for this algorithm is a beautiful O(n) with O(n) memory usage.

However, it's possible to do much better than this. In particular, let's take a look at the first few terms of the sequence, which are

 S(0) = 1
 S(1) = 1
 S(2) = 2
 S(3) = 3
 S(4) = 5

This looks a lot like the Fibonacci sequence, and in fact you might be able to see that

 S(0) = F(1)
 S(1) = F(2)
 S(2) = F(3)
 S(3) = F(4)
 S(4) = F(5)

This suggests that, in general, S(n) = F(n + 1). We can actually prove this by induction on n as follows.

As our base cases, we have that

S(0) = 1 = F(1) = F(0 + 1)

and

S(1) = 1 = F(2) = F(1 + 1)

For the inductive step, we get that

S(n) = S(n - 2) + S(n - 1) = F(n - 1) + F(n) = F(n + 1)

And voila! We've gotten this series written in terms of Fibonacci numbers. This is great, because it's possible to compute the Fibonacci numbers in O(1) space and O(lg n) time. There are many ways to do this. One uses the fact that

F(n) = (1 / √(5)) (Φⁿ + φⁿ)

Here, Φ is the golden ratio, (1 + √5) / 2 (about 1.6), and φ is 1 - Φ, about -0.6. Because this second term drops to zero very quickly, you can get a the nth Fibonacci number by computing

(1 / √(5)) Φⁿ

And rounding down. Moreover, you can compute Φⁿ in O(lg n) time by repeated squaring. The idea is that we can use this cool recurrence:

x⁰ = 1

x²ⁿ = xⁿ * xⁿ

x^{2n + 1} = x * xⁿ * xⁿ

You can show using a quick inductive argument that this terminates in O(lg n) time, which means that you can solve this problem using O(1) space and O(lg n) time, which is substantially better than the DP solution.

Hope this helps!