题目的主要信息:
- 有一对兔子,从出生后第 3 个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第n个月的兔子对数为多少?
我们有如下计算:
月份 | 兔子数(对) |
---|---|
第1个月 | 1对兔子 |
第2个月 | 1对兔子 |
第3个月 | 2对兔子(第一对生出第二对) |
第4个月 | 3对兔子(第一对生出第三对) |
第5个月 | 5对兔子(第一对生出第四对、第二对生出第五对) |
第6个月 | 8对兔子(第一对生出第六对、第二对生出第七对、第三对生出第八对) |
我们发现除了最前面两个月,其余月份的兔子数都是有它前面的两个月相加而来,因此我们有如下结论:,这正是大名鼎鼎的斐波那契数列。
方法一:递归
具体做法:
对于的问题,我们可以每次递归地寻找子问题,然后子问题累得到结果,子问题找到1或者2就停止。
#include<iostream>
using namespace std;
int getSum(int n) { //求每个月兔子数
if(n == 1 || n == 2) //n=1或2跳出递归
return 1;
return getSum(n - 1) + getSum(n - 2); //返回前两个月相加
}
int main(){
int n;
while(cin >> n){ //每次输入n
cout << getSum(n) << endl;
}
return 0;
}
复杂度分析:
- 时间复杂度:,如图所示,树型递归,遍历每个结点
- 空间复杂度:,递归栈最大深度为
方法二:动态规划
具体做法:
除了自上而下的递归,我们还可以利用像上述数组一样的自下而上的相加,反正除了第一二月外,我这个月的值等于它前两个月的值相加,第一二个月都初始化为1,从第三个月开始不断由前两个月累加,直到第个月。转移方程就是:
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
while(cin >> n){ //每次输入n
vector<int> dp(n + 1);
dp[1] = 1; //初始第一个月
dp[2] = 1; //第二个月
for(int i = 3; i <= n; i++) //后面的每个月由前面的累加
dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[n] << endl;
}
return 0;
}
复杂度分析:
- 时间复杂度:,遍历dp数组一次
- 空间复杂度:,动态规划辅助数组dp的长度为
方法三:迭代
具体做法:
注意到方法二动态规划每次循环只使用到了第个变量和第个变量,那我们可以用两个变量不断滚动来优化。
#include<iostream>
using namespace std;
int main(){
int n;
while(cin >> n){ //每次输入n
if(n <= 2) //前两个月直接输出
cout << 1 << endl;
else{
int dpi_2 = 1; //初始化第1个月
int dpi_1 = 1; //初始化第2个月
int output = 0;
for(int i = 3; i <= n; i++){
output = dpi_1 + dpi_2; //公式相加
dpi_2 = dpi_1; //变量更新
dpi_1 = output;
}
cout << output << endl;
}
}
return 0;
}
复杂度分析:
- 时间复杂度:,一次遍历到
- 空间复杂度:,常数级空间