A child is running up a ladder with n steps, and can hop either 1
step or 2 steps at a time. Calculate how many possible ways the child
can run up the ladder.
This problem is similar to Fibonacci Problem. Each step n can be reached from either two steps below (n-2) or one step below (n-1), thus the number of possibilities to reach that step is the sum of the possibilities to reach those other two steps. Base cases would be:
1. If there is only 1 step then child can run up the ladder only one way by taking 1 step.
2. If there are 2 steps then child can run up the ladder 2 ways by taking a single 2 step or taking two 1 steps.
Like the Fibonacci problem,the runtime of this problem is exponential O(2^n)
This problem is similar to Fibonacci Problem. Each step n can be reached from either two steps below (n-2) or one step below (n-1), thus the number of possibilities to reach that step is the sum of the possibilities to reach those other two steps. Base cases would be:
1. If there is only 1 step then child can run up the ladder only one way by taking 1 step.
2. If there are 2 steps then child can run up the ladder 2 ways by taking a single 2 step or taking two 1 steps.
int countWays(int n) { if(n==0) return 0; else if(n==1||n==2) return n; else return countWays(n-1)+countWays(n-2); }
Like the Fibonacci problem,the runtime of this problem is exponential O(2^n)
0 comments:
Post a Comment