Given N count of stairs we want to know how many ways are there to climb all the stairs if we are allowed to climb only one or two stairs at a time.
Solution:
This problem lends itself to dynamic programing using recursion
In order to climb stairs we can take one step which leaves us with N-1 steps and we may take two steps which leaves us with N-2 steps which gives us the following
public int ClimbStairs(int[] memo, int n) {
if (n == 0)// If no stairs
return 0;
if (n == 1)//If one stair to climb then we just take one step
return 1;
if(n==2) //If two stairs to climb then either we can take two single steps or one two step jump. So there are two ways.
return 2;
if (memo[n] == 0) {
int result1 = ClimbStairs(memo, n - 1);
int result2 = ClimbStairs(memo, n - 2);
memo[n] = result1 + result2 ;
}
return memo[n];
}
If the rule was we could take three steps in addition to the one and two steps then we would add one more result
int result3 = ClimbStairs(memo, n - 3);
Note:
This question is almost similar to fibonacci series.
In febonacci we calculate the first two number to get the next number
Same is here, we need the result of all the possible ways to come to one step below and all ways to come to two steps below and we add them together.
In this problem we used dynamic programing memoization technique (top-down) approach. Memoization helps us to store already computed values so that we don't have to compute again and hence more efficient.
We can also use Bottom-up approach of dynamic programing to solve this problem using iteration instead of recursion.