Chuyển tới nội dung chính
DSAQuy hoạch động

Fibonacci Bottom-up

Học cách giải bài Fibonacci bằng quy hoạch động bottom-up.

Độ khóCơ bản
Thời lượng25 phút
Thẻdsa, dynamic-programming, fibonacci, bottom-up

Mục tiêu học tập

  • Hiểu ý tưởng quy hoạch động bottom-up qua bài Fibonacci.
  • Biết cách xây bảng giá trị từ bài toán nhỏ đến bài toán lớn.
  • Viết được code Fibonacci bottom-up bằng C++ và Python.
  • Phân tích được độ phức tạp thời gian và bộ nhớ của lời giải.

Kiến thức cần có

  • Biết khái niệm biến và vòng lặp.
  • Hiểu mảng/list ở mức cơ bản.
  • Biết định nghĩa dãy Fibonacci.

Video bài học

Lý thuyết

Dãy Fibonacci được định nghĩa như sau:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n - 1) + F(n - 2) với n >= 2

Cách bottom-up bắt đầu từ hai giá trị nhỏ nhất, sau đó xây dần các kết quả lớn hơn. Thay vì gọi đệ quy nhiều lần, ta lưu lại kết quả đã tính và dùng chúng để tính bước tiếp theo.

Với n = 6, ta tính lần lượt:

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8

Ý tưởng quan trọng: mỗi trạng thái F(i) chỉ phụ thuộc vào hai trạng thái trước đó là F(i - 1) và F(i - 2).

Trực quan hóa

Fibonacci Bottom-up

Bảng dp từ F(0) đến F(6)

Bước 1/7
F(0)0
F(1)?
F(2)?
F(3)?
F(4)?
F(5)?
F(6)?
i0
dp[i - 2]-
dp[i - 1]-
dp[i]0

Khởi tạo F(0) = 0.

dp[0] = 0dp[1] = 1for i = 2..n:    left = dp[i - 2]    dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

Ví dụ code

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

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    cout << fibonacci(6);
    return 0;
}

Kết quả chương trình

Kết quả chương trình

Khu vực này sẽ hiển thị output hoặc kết quả chạy chương trình khi Code Runner được triển khai.

8

Độ phức tạp

Độ phức tạp thời gianO(n)
Độ phức tạp bộ nhớO(n)

Ta duyệt từ 2 đến n, nên thời gian là O(n). Mảng dp có n + 1 phần tử, nên bộ nhớ là O(n).

Lỗi thường gặp

  • Quên xử lý trường hợp n = 0 hoặc n = 1.
  • Tạo mảng dp không đủ kích thước.
  • Dùng lại công thức đệ quy nhưng không lưu kết quả, khiến thời gian tăng rất nhanh.
  • Nhầm thứ tự cập nhật khi tối ưu bộ nhớ xuống O(1).

Quiz

Quiz Fibonacci

Kiểm tra hiểu bài Bottom-up

0/4
1. Trong lời giải Fibonacci bottom-up, hai giá trị nào cần khởi tạo trước?
2. Công thức chuyển trạng thái đúng là gì?
3. Với n = 6, kết quả F(6) là bao nhiêu?
4. Nếu dùng mảng dp từ 0 đến n, độ phức tạp bộ nhớ là gì?

Luyện tập

  1. Tính `F(10)` bằng bảng bottom-up và ghi lại từng giá trị.
  2. Sửa code để chỉ dùng hai biến thay vì mảng `dp`.
  3. Viết hàm trả về toàn bộ dãy Fibonacci từ `F(0)` đến `F(n)`.

Tóm tắt

Bottom-up là cách giải từ bài toán nhỏ lên bài toán lớn. Với Fibonacci, ta bắt đầu từ F(0) và F(1), sau đó tính từng giá trị tiếp theo bằng công thức F(i) = F(i - 1) + F(i - 2).

Cách này tránh việc tính lặp lại như đệ quy thuần và là ví dụ nhập môn tốt cho Quy hoạch động.