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;
}
Comments