Sinh dãy Fibonacci

Dãy Fibonacci: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Sử dụng quy hoạch động (bottom-up) để tính hiệu quả, tránh đệ quy lặp lại.

Đầu vào và Đầu ra

Đầu vào: n = 10
Đầu ra: 10th Fibonacci Terms: 55

Thuật toán

1. Tạo mảng fibo kích thước n+2.
2. fibo[0]=0, fibo[1]=1.
3. Với i từ 2 đến n: fibo[i] = fibo[i-1] + fibo[i-2].
4. Trả về fibo[n].

Độ phức tạp: O(n) thời gian, O(n) không gian (có thể tối ưu về O(1) không gian).

Ví dụ C++

#include <iostream>
using namespace std;

int genFibonacci(int n) {
    int fibo[n+2];
    fibo[0] = 0; fibo[1] = 1;
    for (int i = 2; i <= n; i++)
        fibo[i] = fibo[i-1] + fibo[i-2];
    return fibo[n];
}

int main() {
    int n;
    cout << "Enter number of terms: "; cin >> n;
    cout << n << "th Fibonacci Terms: " << genFibonacci(n);
}

Kết quả

Enter number of terms: 10
10th Fibonacci Terms: 55