🎯 Mục tiêu bài học

• Hiểu tư tưởng ghi nhớ kết quả (memoization) trong quy hoạch động.
• So sánh tốc độ giữa Fibonacci thường và có nhớ kết quả.

📘 Lý thuyết

Bài toán Fibonacci là ví dụ kinh điển của đệ quy lặp lại nhiều lần:

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

Khi không nhớ kết quả, các lời gọi trùng lặp sẽ khiến chương trình cực kỳ chậm. 👉 Giải pháp: lưu các giá trị đã tính để dùng lại.

💻 Thực hành

C++

#include 
using namespace std;
vector f(100, -1);
long long fib(int n){
    if(n<=1) return n;
    if(f[n]!=-1) return f[n];
    return f[n]=fib(n-1)+fib(n-2);
}
int main(){
    int n;cin>>n;
    cout<

from functools import lru_cache
@lru_cache(None)
def fib(n):
    if n<=1: return n
    return fib(n-1)+fib(n-2)
print(fib(int(input())))

# Python
cnt=0
def fib(n):
    global cnt
    cnt+=1
    if n<=1: return n
    return fib(n-1)+fib(n-2)
print(fib(10),"calls=",cnt)