Climbing Stairs
Easy · Dynamic Programming · about 10 minutes
Asked at Amazon, Apple, Google.
A staircase has n steps, and with each stride you go up either 1 step or 2 steps. Count the different sequences of strides that take you exactly to the top.