分治与动态规划------斐波那契数列
通过看斐波那契数列来看分治跟动态规划的区别，所耗费的时间动态规划的可以达到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;a = 1;for(i=2; i<=n; i++){a = a + a;}printf("%d\n", a);}return 0;}*/
页:
[1]