Find the number of possible ways one can traverse a n-step staircase
Problem: Find the number of possible ways one can traverse a n-step staircase (moving in one direction only) using any combination of 1-step, 2-step, and 3-step jumps.
Solution:
// recursive
int count(int n) {
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
return count(n - 3) + count(n - 2) + count(n - 1);
}
// dynamic programming
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
int a = 1;
int b = 1;
int c = 2;
int d = a + b + c;
for (int i = 3; i < n; i++) {
a = b;
b = c;
c = d;
d = a + b + c;
}
return d;
// template meta-programming
template<int N>
struct count {
static const int value = count<N-3>::value + count<N-2>::value + count<N-1>::value;
};
template<>
struct count<0> {
static const int value = 1;
};
template<>
struct count<1> {
static const int value = 1;
};
template<>
struct count<2> {
static const int value = 2;
};