首先来看看题目的要求:空间复杂度 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; }