### 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;`
`}`