最简单的斐波纳契数列的递归推导式为：dp[n]=dp[n-1]+dp[n-2];
最简单的例子：一对小兔子在出生的第三个月后可以繁殖并每月生一对小兔子，兔子的总对数就是兔子序列：1 1 2 3 5 8...
其实我们可以重新思考一下原来的递推公式：兔子分两类：不具有繁殖能力的幼年期和具有繁殖能力的成年期
假设B[i]为第i年新出生的兔子数量
根据成年即可生育的设定 第i年新出生的兔子数量就是第i年的成年的数量
显然有：B[n]=B[n-2];
A [n]=B[n-1];
sum[i]=A[i]+b[i];
SkyLee的艾露猫
#include <cstdio> int A[46], B[46], C[46],T, N; void Calculate() { //易知B[i]为第i年新出生的艾露猫数量，则各数据均可求 //初始化前几年数据，因为考虑到最开始的一对艾露猫为第一年新出生，为计算方便B[1]设置为2 A[1] = A[2] = A[3] = 2; B[1] = B[3] = 2; for (int i = 4; i < 46; i++) { //成年数量为前一年数量加上刚成年的数量减去进入老年数量 B[i] = B[i - 1] + B[i - 2] - B[i - 12]; //未成年数量为前一年新出生数量加上今年新出生数量 A[i] = B[i] + B[i - 1]; //老年数量为前一年老年数量加上刚进入老年数量减去死亡数量 C[i] = C[i - 1] + B[i - 12] - B[i - 20]; } //将B[1]置为0 B[1] = 0; } int main() { Calculate(); scanf("%d", &T); while (T--) { scanf("%d", &N); printf("%d ", A[N] + B[N] + C[N]); } }
AlvinZH去图书馆
一道比较有意思的斐波那契类型的题目。
斐波纳契类型的题目无非是递归+状态转移，所以较难一点的递归都用到了两个以上的状态转移数组，搞清楚每个状态转移数组所代表的具体含义即可A
#include <cstdio> using namespace std; int n; long long ans[52]; long long res[52]; int main() { res[0]=1; res[1]=2; res[2]=3; ans[0]=1; ans[1]=2; ans[2]=4; for(int i=3;i<52;i++){ ans[i]=ans[i-1]+ans[i-2]+res[i-3]; res[i]=ans[i-1]+ans[i-2]; } while(~scanf("%d",&n)) printf("%lld ",ans[n-1]); }
本题可以运用递推的方法解决。
因为只能进行1, 2, 3步的跨越，所以某步的种数等于前三步种数之和。但是由于不能连续两次直接跨三步的操作，因此对递推还要有所改良。
先看总体思路，可以选择1, 2, 3步进行跨越，因此显然有ans[n]=ans[n-1]+ans[n-2]+ans[n-3]，即可以分别从前1个，前2个，前3个砖进行跨越。但还要考虑不能连续进行两次“3格”跨越，简称“跨3”，因此原式要进行修改，即为ans[n]=ans[n-1]+ans[n-2]+res[n-3]，达到n之前的最后一步跨1和跨2都没有影响，不存在“连续跨3”的非法情况，因此ans[n-1]和ans[n-2]可以直接加到ans[n]上。问题在于跨3之前的最后一步不能“跨3”，否则就连续两次“跨3”操作了，但ans[n-3]是有可能最后一步跨3的，因此要改用res来表示最后一步“跨3”的情况。现在来看如何定义res数组以及res的递推公式，res[i] 代表第 i 步之前的最后一步（即第 i-1 步）进行了跨3，因此 res[i] 不能够从 res[i-3] 通过一次跨3操作到达，所以显然有 res[n]=ans[n-1]+ans[n-2]，这样就排除了连续两次跨3的问题。
最终递推式：
ans[i]=ans[i-1]+ans[i-2]+res[i-3] , res[i]=ans[i-1]+ans[i-2]
递推的时间复杂度为O(n)。