Finding the number of ways to climb the stairs - Part 2

Problem

You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase ?

For example, If there are 3 stairs, there are three possible ways to climb them.

{1,1,1}, {1, 2}, {2, 1}

Your algorithm should print out the total number of ways to climb the stairs. (Optional: should also print out the different ways as above)

The previous solution in Part 1, was too slow. 

Using dynamic programming we can do better.

Instead of calculating the ways of climbing the stairs from the beginning of the staircase, we can calculate from the end of the staircases, Nth stair.

To reach the Nth stair, given the options of either 1 stair or 2 stairs each time, one should be from either the N-1th stair or the N-2th stair.

If there are n and m ways of reaching the N-1th and N-2th stair respectively.
The total ways of reaching the Nth stairs will be (n + m). We can write the algorithm as below:

W(N) = W(N-1) + W(N-2), where W(x) denotes the ways of climbing to the x th stair.

To use dynamic programming, we need to define the base case correctly.

W(1) = 1, W(2) = 2
After that, we can loop from 3 to N to find out W(N).  We should remember to store W(i-1) and W(i) after each iteration so that we can use them as W(i-1) and W(i-2) in the next iteration. This will take O(N), where N is the number of stairs.

In each iteration, we also use the list to keep track of the steps we took to climb to I th stairs as well. This takes up to  O(M), where M is the number of ways to climb to the Nth stair.
Therefore, the overall time complexity is O(MN). The following is the complete code.

If the question is just to print out a total number of ways to climb the stairs, the following algorithm can do the job in O(N).

Practice statistics
31 mins: to write up the code and fix the bug. Made a logical mistake and had to use the compiler to find it.

UPDATE (2019-07-27): solved the problem again in python.
It is the third time to solve this problem.


Practice statistics

3:48: to write up the code
1:02: to review the code

UPDATE (2023-02-28): solved the problem again. This time I added the additional logic to print out the actual permutations.

Practice statistics

10 mins: to come up with an algorithm

15 mins: to write up the algorithm with one bug

1 min: to fix the bug

1hr: to add additional logic to print the ways of climbing the stairs. Got messed up with the array generation.