Count ways to climb steps
Find the number of ways to reach the top of the stairs given that there are N steps in total. A person can climb 1, 2 or 3 steps at a time.
/*
* NoWaysToClimbSteps.cpp
*
* Created on: May 10, 2012
* Author: Kiran Hegde
*/
#include <iostream>
using namespace std;
/**
* Since 1, 2 or 3 steps can be climbed at a time,
* The last step can be reached from the (last - 1), (last - 2) and
* (last - 3) steps. Each of these steps in turn can be reached in a
* similar manner. Recursive solution.
*/
int countWays(int noSteps, int *cache) {
if (noSteps < 0) {
return 0;
}
else if (noSteps == 0) {
return 1;
}
else if (cache[noSteps] >= 0) {
return cache[noSteps];
}
else {
cache[noSteps] = countWays(noSteps - 1, cache) +
countWays(noSteps - 2, cache) +
countWays(noSteps - 3, cache);
return cache[noSteps];
}
}
/**
*
*/
int countWays(int noSteps) {
int *cache = new int[noSteps+1];
for (int i=0; i<noSteps+1; i++) {
cache[i] = -1;
}
int result = countWays(noSteps, cache);
delete[] cache;
return result;
}
/**
* Test the code
*/
int main() {
// Assume that there are 25 steps in total
int noSteps = 25;
cout << "No of ways to climb " << noSteps << " steps: " <<
countWays(noSteps) << endl;
return 0;
}