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

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

通过看斐波那契数列来看分治跟动态规划的区别，所耗费的时间动态规划的可以达到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;
}*/