algorithm - n steps with 1, 2 or 3 steps taken. How many ways to get to the top?

Question

If we have n steps and we can go up 1 or 2 steps at a time, there is a Fibonacci relation between the number of steps and the ways to climb them. IF and ONLY if we do not count 2+1 and 1+2 as different.

However, this no longer the case, as well as having to add we add a third option, taking 3 steps. How do I do this?

What I have:

1 step = 1 way
2 steps = 2 ways: 1+1, 2
3 steps = 4 ways: 1+1+1, 2+1, 1+2, 3

I have no idea where to go from here to find out the number of ways for n stairs

I get 7 for n = 4 and 14 for n= 5 i get 14+7+4+2+1 by doing the sum of all the combinations before it. so ways for n steps = n-1 ways + n-2 ways + .... 1 ways assuming i kept all the values. DYNAMIC programming. 1 2 and 3 steps would be the base-case is that correct?

Answer 1

I would say that the formula will look in the following way:

K(1) = 1
K(2) = 2
k(3) = 4
K(n) = K(n-3) + K(n-2) + K(n - 1)

The formula says that in order to reach the n'th step we have to firstly reach:

• n-3'th step and then take 3 steps at once i.e. K(n-3)
• or n-2'th step and then take 2 steps at once i.e. K(n-2)
• or n-1'th step and then take 1 steps at once i.e. K(n-1)

K(4) = 7, K(5) = 13 etc.

You can either utilize the recursive formula or use dynamic programming.