Dãy số Fibonacci được xây dựng như sau :
f[1] = 1
f[2] = 1
f[i] = f[i-1] + f[i-2]
Đề bài bắt ta tìm số Fibonacci thứ n
Để làm bài này, ta có thể dùng hàm đệ quy nhưng lại gặp vấn đề thời gian vì n <= 80
Chúng ta có thể làm bằng cách quy hoạch động như sau :
B1 : nhập n
B2 : gán phần thử đầu tiên và thứ 2 bằng 1
B3 : duyệt i chạy từ 3 đến n với công thức f[i] = f[i-1] + f[i-2] để tìm số Fibonacci thứ i
B4 : in ra số fibonacci thứ n ( ghi ra f[n] )
Code C++
```
#include<bits/stdc++.h>
using namespace std;
int n;
long long f[100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
f[1]=1;f[2]=1;
for(int i=3;i<=n;++i){
f[i]=f[i-1]+f[i-2];
}cout<<f[n];
return 0;
}
```