Understanding Permutations

Lets say that you’re given a number which represents an amount of stairs. You can only walk up 1 step at a time or two steps at a time or a combination of both. Find the total number of ways you can climb up the stairs.

Thanks, I’m not asking for the answer, but just a few pointers to get started


Input: 3

1.) 1 + 1 + 1

2.) 1 + 2

3.) 2 + 1

Answer: 3

Saying anything at all immediately solves it
analyze the problem, look at what affects what, start with a small inputs and consider how you do it manually…same as any other problem.

but what if I get a stair case of 50? How th am I supposed to calculate that? there’s too many permutations

I dont know what you mean

step 50 is computable with pen and paper, and doing that forces you to consider how things relate to one another

I solved it. I did it for the first few and found the fibonacci sequence

but how does it relate to that sequence?

if fib(i) is fib(i-1) + fib(i-2), how does that relate to the number of ways you can get to a particular step?
or better yet, write it as: step(i) = step(i-1) + step(i-2)

and, what if 3 steps was allowed as well, what would the sequence be then?

there’s also at least one other way to solve it, by computing the number of permutations of steps that can be used, indeed, your title is a solution to the problem

Number of ways (number of steps): (1, 1), (2, 2), (3,3), (4, 5), (5, 8), (6, 13), (7, 21), (8, 34)

Its not exact in the beginning but nonetheless the pattern is contained throughout.

Permutation method might have a faster run time

It is the same in the beginning. You just need to consider one step earlier as well.

To reach a step i, you can either take 1 step from the previous one (i-1) or two steps from the one before that (i-2) so the number of ways to reach step i is therefore the sum of both.

If you’re allowed to take 3 steps at once as well, then you would also need to add i-3