CODEWITHSUNDEEP
algorithmrecursiondynamic-programming
user3126404
user3126404

Reputation:

Recursion and n-stair example in DP

I am new to dynamic programming and came over this example.

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.

The solution was ..T(n) = T(n-1) + T(n-2)

What was the last step I did.?

I was either at n-1 step or n-2 step. Now How can the number of ways to reach Nth step be the sum of the number of ways to reach n-1 steps and n-2 steps. I am not able to get the intuition required to strike the logic.Please help.

P.S I can write code for this in recursion.

Upvotes: 0

Views: 776

Answers (3)

Olavi Mustanoja
Olavi Mustanoja

Reputation: 2065

Dynamic programming solution

T(n) = T(n-1) + T(n-2) is basically the recursion algorithm for finding the nth fibonacchi number. Now, if I understood your question correctly, you are trying to find a dynamic programming solution for this.

With DP we simply keep a memory of the previous answers, and calculate a new answer from the previous ones. This basically boils down to this:

int[] s = new int[n]
s[0] = 0;
s[1] = 1;

for(int i = 2; i < n; i++) {
    s[i] = s[i - 1] + s[i - 2];
}

return s[n - 1] + 1;

Where n is the number of steps and s[n - 1] + 1 is the number of ways to reach the nth step.

Therefore for 2 steps the solution is (1) + 1 = 2:

1 + 1
2

for 3 steps the solution is (1 + 1) + 1 = 3:

1 + 1 + 1
1 + 2
2 + 1

for 4 steps the solution is (1 + 1 + 2) + 1 = 5

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

for 5 steps the solution is (1 + 1 + 2 + 3) + 1 = 8

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 2 + 1 + 1
2 + 1 + 1 + 1
1 + 2 + 2
2 + 1 + 2
2 + 2 + 1

Let us go deeper

What was the last step I did?

This cannot be determined with the information we have been given. The last step depends purely on what order we choose to walk the steps. What we can do, however, is find the probability of the last step being a 2-step or 1-step. As you can see from the illustrations above, the probability for the last step being 1 is:

P(1) = 1 / 1 = 100.0%
P(2) = 1 / 2 =  50.0%
P(3) = 2 / 3 =  66.6%
P(4) = 3 / 5 =  60.0%
P(5) = 5 / 8 =  62.5%

As we can see, the numerator and denominator both follow the same pattern; the numerator is just one fibonacchi number ahead of the denominator.

Thus, the probability for the last step to be 1:

F(n) = F(n - 1) + F(n - 2), F(0) = 0, F(1) = 1, n >= 0

P(n) = F(n) / F(n - 1), n >= 2

The recursion formula for 1 / P(n) actually limits at (1 + sqrt(5)) / 2 when n approaches infinity, which is probably better known as the Golden ratio.

Knowing this, the probability for the last step to be 1 is 1 / ((1 + sqrt(5) ) / 2), which can also be written out as 2 / (1 + sqrt(5) ). Because this is >0.5, we can say that the last step was probably 1.

You can see the complete computation in Wolfram Alpha.

Upvotes: 1

totoro
totoro

Reputation: 3407

Now How can the number of ways to reach Nth step be the sum of the number of ways to reach n-1 steps and n-2 steps.

Think this way. 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). Hope this helps!

Upvotes: 0

Herokiller
Herokiller

Reputation: 2991

The ways to reach (n-2)th step and then make a 2-step, and the ways to reach (n-1)th step and make a 1-step do not intersect, because its' last step is different and there are no other way to reach n-th, without bypassing (n-1) or (n-2), and those were already calculated for (n-1) and (n-2)

Upvotes: 0

Related Questions