统计每个月兔子的总数（牛客）

题目描述：

有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？

输入描述：输入int型表示month

9

输出描述：输出兔子总数

34

解题思路：

第n个月的总兔子数 = 第n-1个月的总兔子数 + 第n-2个月的总兔子数

因为第n-1个月的兔子不会再生，但这部分兔子也是第n个月的兔子中的一部分

而第n-2个月的所有兔子，各自都会再产生一只兔子，所以这是第n个月兔子中的另一部分

即递归方程：

f(1)=1

f(2)=1

f(n) = f(n-1) + f(n-2)   ;n>=3

AC代码：

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int month;

	while (cin >> month) {
		vector<int> number;
		number.push_back(0);
		
		number.push_back(1);
		number.push_back(1);
		
		for(int i=3; i<=month; i++){
			int k = number[i-1]+number[i-2];
			number.push_back(k);
		}
		
		cout<<number[month]<<endl;
	}

	return 0;
}

我自己还有一种比较繁琐的方法，代码通过率只有70%，没通过的30%应该是迭代次数过多，时间复杂度超了。也保存在这儿吧

代码：

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	int month;

	while (cin >> month) {
		vector<int> number;
		int total = 1;
		number.push_back(month - 2);
		while (!number.empty()) {
			total += number[0]; //把有效数据加入
			cout << "total+=" << number[0] << endl;  //打印中间过程，提交时删除此句

			number[0] -= 2; //将产生的新的有效数据加入
			if (number[0] >= 1) {
				while (number[0] > 0) {
					number.push_back(number[0]);
					cout << number[0] << "入栈" << endl;   //打印中间过程，提交时删除此句
					number[0]--;
				}
			}

			number.erase(number.begin());
		}

		cout << total << endl;
	}

	return 0;
}