每日一题 No.15 兔子繁殖问题（斐波那契数列）

本题要求：

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么n个月以后共有多少对兔子？

输入格式：

输入一个数n (1<=n<=1000)

输出格式：

输出兔子的对数

输入样例：

1000

输出样例：

9079565065540428013

解题思路 :

运用记忆化搜索，详情看背包问题

代码 :

#include <iostream>

using namespace std;  

long long d[1001] = {0};

long long a(int i) {
if (d[i] != 0) {
return d[i];
    }
if (i <= 2) {
        d[i] = 1;
    } else {
        d[i] = a(i - 1) + a(i - 2);
    }
return d[i];
} 

int main() {
int month;
long long sum = 0;
cin >> month;
for (int i = 0; i < month; i++) {
        sum += a(i);
    }
cout << sum << endl;
return 0;  
}