An elf has a staircase with 10 steps to climb. Each step it takes can cover either one stair or two stairs. In how many ways can the elf climb the stairs?
5 Doubles === 1 way
4 Doubles, 2 Singles === e.g. DDSSDD
number of ways = 6!/(2!4!) or C(6,4) = 15
3 Doubles, 4 Singles === C(7,3) = 35
2 Doubles , 6 Singles === C(8,2) = 28
1 Double , 8 Singles === C(9,1) = 9
10 Singles === 1
total = 89
i don't understand how its 89 ways!
how about 20 stairs, and N stairs? what would be the equation for that?
To find the number of ways the elf can climb the stairs, we can use the concept of dynamic programming. We'll create an array to store the number of ways to reach each step.
Let's initialize an array called `ways`, where `ways[i]` will represent the number of ways to reach the `i-th` step. We can then define the base cases as follows:
- If there are 0 steps or 1 step, there is only one way to reach that step.
- If there are 2 steps, there are two ways to reach the top: one step at a time or two steps at once.
We can fill in the rest of the array using the recurrence relation: `ways[i] = ways[i-1] + ways[i-2]`. This means that to reach the `i-th` step, the elf can either take one step from the `i-1` step, or two steps from the `i-2` step.
Here's the Python code to find the number of ways to climb the stairs:
```python
def count_ways(n):
ways = [0] * (n+1)
ways[0] = 1
ways[1] = 1
ways[2] = 2
for i in range(3, n+1):
ways[i] = ways[i-1] + ways[i-2]
return ways[n]
n = 10
result = count_ways(n)
print(result)
```
In this case, the elf can climb the 10-step staircase in 89 different ways.