n-stair / step climbing problem: cannot conceptualize why T(n) = T(n-1) + T(n-2)

user_401360 0
Viewed 113

I'm having trouble conceptually understanding the solution to the well-known n-stair climbing problem. The n-stair problem is:

You have n-steps to climb. You can only climb 1 or 2 steps at a time. find the number of ways to reach Nth step.

To keep it simple, let's just use the case where n = 2. The solution is T(n) = T(n-1) + T(n-2) and this is of course the Fibonacci sequence.

The explanation as to why usually goes something like this:

You are at the nth step. How did you get there given that you could climb 1 step or 2 at a time? Well, your previous step must be at either step n-1 (took 1 step) or step n-2 (took 2 steps). Now, there are T(n-1) ways to reach the n-1th step, and T(n-2) ways to reach n-2th steps, which means that there are T(n-2) ways to reach n if your last step was at n-2, and T(n-1) ways to reach n if your last step was at n-1. Those are the only two possibilities of how you finally reached n, so the total number of ways to get to nth step is T(n-1) + T(n-2)

I have trouble conceptualizing the part below:

there are T(n-1) ways to reach the n-1th step, and T(n-2) ways to reach n-2th steps, which means that there are T(n-2) ways to reach n if your last step was at n-2, and T(n-1) ways to reach n if your last step was at n-1.

This sounds wrong. The explanation seems to contradict itself.

there are T(n-1) ways to reach the n-1th step

and

and T(n-1) ways to reach n if your last step was at n-1

And similarly for T(n-2)

I also get confused on a second point. When we say that the solution is T(n-1) + T(n-2) my brain shouts out 'but wait a minute, you're double-counting. T(n-1) already includes T(n-2)'.

Can someone help me conceptually understand the reason why T(n) = T(n-1) + T(n-2)

PS This is not question regarding implementing a solution, but rather a question as to how to explain/understand the answer.

fibonacci dynamic-programming recursion algorithm
2 Answers

the reason why T(n) = T(n-1) + T(n-2)

The post you quote takes (what seems to me to be) the odd step of looking at the end of the process.

Let's instead consider what happens when we are at the start of the process, at the bottom of a staircase of n steps. What can we do right now?

  • We can take 1 step, which leaves us with the n-1 problem to solve

OR

  • We can take 2 steps, which leaves us with the n-2 problem to solve.

Clearly, we either do one or the other. So the number of ways of solving the n problem is precisely the number of ways of solving the n-1 problem PLUS the number of ways of solving the n-2 problem.

Or, T(n) = T(n-1) + T(n-2).

user_710590

Of course, you count some duplicate path in T(n-1) and T(n-2). But, the last step to the final is different! So, think like this. The last step could be 1 or 2. Now, from this separation, you will have a different path and you shouldn't worry about anything in the modeling.

user_37688710
Related