Hiểu bài toán

Cho một số nguyên dương n (1 ≤ n ≤ 10^6). Yêu cầu tính số Fibonacci thứ n theo định nghĩa: F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 (n ≥ 3). Kết quả cần in ra là số dư của Fn khi chia cho 1,000,007 (10^6 + 7). Do n có thể lên tới 10^6, các phép tính phải được thực hiện hiệu quả và tránh tràn số.

Các cách tiếp cận

Cách Quy hoạch động cơ bản

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000007;

int main() {
    int n;
    cin >> n;
    // Sử dụng vector để lưu trữ các giá trị F[i]
    vector<long long> F(n + 1);

    if (n >= 1) F[1] = 1;
    if (n >= 2) F[2] = 1;

    for (int i = 3; i <= n; i++) {
        F[i] = (F[i-1] + F[i-2]) % MOD;
    }

    cout << F[n];
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận trực tiếp nhất. Ta tạo một mảng (vector) F có kích thước n+1. Khởi tạo hai giá trị đầu tiên là 1. Sau đó, lặp từ i = 3 đến n, tính F[i] bằng tổng hai giá trị trước đó (F[i-1] và F[i-2]) và lấy modulo ngay lập tức để tránh tràn số. Mảng này lưu trữ toàn bộ dãy Fibonacci từ 1 đến n. Phương pháp này dễ hiểu nhưng tốn bộ nhớ.

Cách Quy hoạch động tối ưu (Không gian)

#include <iostream>
using namespace std;

const int MOD = 1000007;

int main() {
    long long n;
    cin >> n;

    long long f1 = 1, f2 = 1;

    if (n == 1 || n == 2) {
        cout << 1;
        return 0;
    }

    long long f3;
    for (int i = 3; i <= n; i++) {
        f3 = (f1 + f2) % MOD;
        f1 = f2;
        f2 = f3;
    }

    cout << f2;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách này tối ưu bộ nhớ. Thay vì lưu trữ toàn bộ dãy, ta chỉ cần 3 biến: f1, f2, và f3. f1 và f2 lưu trữ hai số Fibonacci liên tiếp hiện tại. Trong mỗi bước lặp, f3 được tính là tổng của chúng, sau đó f1 và f2 được cập nhật để chuẩn bị cho bước tiếp theo (f1 thành f2 cũ, f2 thành f3 mới). Cuối cùng, f2 sẽ chứa giá trị Fn. Đây là lựa chọn tối ưu cho dữ liệu đầu vào lớn (n ~ 10^6) về cả thời gian và bộ nhớ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Luôn thực hiện phép chia lấy dư (modulo) trong mỗi bước tính toán để đảm bảo giá trị số nằm trong giới hạn cho phép và tránh tràn số, đặc biệt khi n lớn.
• Bài toán Fibonacci có tính chất đệ quy nhưng quy hoạch động (hoặc lặp) hiệu quả hơn hẳn đệ quy tuần tự do tính toán các giá trị đã qua.
• Với n lên tới 10^6, việc sử dụng mảng 1 chiều O(n) là chấp nhận được về thời gian nhưng tốn bộ nhớ. Giải pháp O(1) về bộ nhớ là tối ưu nhất.

Lỗi thường gặp

• Quên thực hiện phép chia lấy dư ngay trong vòng lặp, dẫn đến tràn số biên (overflow) khi F[i] trở nên quá lớn.
• Lỗi truy cập chỉ số mảng: Mảng cần có kích thước tối thiểu là n + 1 (nếu dùng mảng static hoặc vector), và cần xử lý đúng các trường hợp n = 1 hoặc n = 2.
• Sử dụng biến có kiểu dữ liệu quá nhỏ (như int thay vì long long) cho các biến lưu trữ số Fibonacci, vì giá trị của chúng có thể lớn hơn 2^31 - 1 trước khi chia lấy dư.