题解 | #斐波那契数列#
斐波那契数列
https://www.nowcoder.com/practice/ee5d403c1172487f8c7915b3c3d924c6
首先来看看题目的要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn)的解法~~~
那么首先回忆一下斐波那契数列，作为dp的入门题，斐波那契作为数学和许多书中的动归入门题
相信递归的方程式对于大家而言并不难
就是dp[i]=dp[i-1]+dp[i-2];
然后不断递归下去~~~但是要注意了这里空间复杂度是有要求的
所以可以利用滚动数组的思想，不难发现递归方程式只有三项，其中一项未知数，然后剩下的两项可以在递归的时候动态保存
具体可以看代码~~
int main()
{
int n;
scanf("%d", &n);
int a=1,b=1,sum=0,i;
if(n<=2)
{
printf("1");
return 0;
}
for(i=2; i<n; i++)
{
sum = a+b;
a = b;
b = sum;
}
printf("%d", sum);
return 0;
}
投递小米集团等公司7个岗位 >