CC150 9.1

9_1.cpp

/* CC150 9.1 */

#include <iostream>

using namespace std;

int countSteps(int n)
{
	if (n < 0)
		return -1;
	int *count = new int[n+1];
	for (int i = 0; i <= n; ++i) {
		if (i == 0)
			count[i] = 1;
		else if (i == 1)
			count[i] = 1;
		else if (i == 2)
			count[i] = 2;
		else
			count[i] = count[i - 1] + count[i - 2] + count[i - 3];
	}
	return count[n];
}

int main()
{
	int n;
	cin >> n;
	cout << countSteps(n) << " possible ways to run up the stairs" << endl;
//	for (int i = 0; i <= n; ++i)
//		cout << countSteps(i) << " possible ways to run up to stair " << i << endl;
	return 0;
}

output

1 possible ways to run up to stair 0
1 possible ways to run up to stair 1
2 possible ways to run up to stair 2
4 possible ways to run up to stair 3
7 possible ways to run up to stair 4
13 possible ways to run up to stair 5
24 possible ways to run up to stair 6
44 possible ways to run up to stair 7
81 possible ways to run up to stair 8
149 possible ways to run up to stair 9
274 possible ways to run up to stair 10