Fibonacci（动态规划）_fibonacci 动态规划

• 斐波那契数列：1、1、2、3、5、8、13、21、34
• 以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

• 动态规划会将求解子问题的解保存下来，来避免下次遇到相同子问题时的重复计算

#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
int dp[N];//dp[]记录每次求解的结果，dp[]为0表示f[]未计算过 
int fibonacci(int n){//第n个斐波那契数 
	if(n==0)return 0; 	
	else if(n==1)return 1;
	else{
		if(dp[n])return dp[n];
		else return dp[n]=fibonacci(n-1)+fibonacci(n-2);
	}
} 
int main(){
	ios::sync_with_stdio(false);
	int n;
	while(cin>>n){
		cout<<fibonacci(n)<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19