分治与动态规划------斐波那契数列

中国小虫

通过看斐波那契数列来看分治跟动态规划的区别，所耗费的时间动态规划的可以达到O(N)的时间复杂度。
/*//婓波那契----分治//#include<stdio.h>int F(int n){    if(n == 1||n == 2)     {          return 1;      }return F(n-1) + F(n-2);}int main(void){int n;while(scanf("%d", &n) != EOF){printf("%d\n", F(n));}return 0;}//婓波那契----动态规划//#include<stdio.h>int main(void){long n, *a, i;while(scanf("%ld", &n) != EOF){a = malloc((n + 1) * sizeof(int));a[0] = 0;a[1] = 1;for(i=2; i<=n; i++){a[i] = a[i-1] + a[i-2];}printf("%d\n", a[n]);}return 0;}*/