算法-每天一道题（21）-上台阶-斐波拉契数列

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或者二级，要走上m级，共有多少走法？注：规定从一级到一级有0种走法。
给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100。为了防止溢出，请返回结果Mod 1000000007的值。

测试样例：

3

返回：

2

C++

#include <vector>
#include <iostream>

using namespace std;
class GoUpstairs {
public:
	int countWays(int n) {
		// write code here
		vector <long long> vec;
		if (n <= 3)
			return n - 1;
		for (int i = 0; i <= 3; i++)
			vec.push_back(i - 1);

		for (int i = 4; i <= n; i++)
			vec.push_back((vec[i - 1] + vec[i - 2]) % 1000000007);

		return vec[n];
	}
};

int main()
{
	GoUpstairs *goupstairs = new GoUpstairs();
	cout << goupstairs->countWays(88) << endl;
	system("pause");
	return 0;
}

/*
解题思路：

斐波拉契数列
*/