C语言训练-斐波纳契数列 （C语言代码）DP

解题思路:

                最后别递归（因为重复子问题太多了），除非你用记忆化递归    T = O(nlogn)；

                最简单的DP吧！(T = O(n))。

注意事项:

参考代码:

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <functional> 
#include <iostream>
#include <algorithm>
using namespace std;
int dp[40];
int main()
{
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
	{
		if( i == 1 || i == 2)
		{
			dp[i] = 1;
		}
		else
		{
			dp[i] = dp[i-1] + dp[i-2];
		}
		if(i < N)
		{
			printf("%d ", dp[i]);
		}
	}
	printf("%d\n", dp[N]);
	return 0;
}