Tính Số Fibonacci Bằng Quy Hoạch Động 1D

Mô tả bài toán

Dãy số Fibonacci được định nghĩa đệ quy:

• F(0) = 0
• F(1) = 1
• F(N) = F(N-1) + F(N-2) với mọi N ≥ 2.

Nếu dùng đệ quy ngây thơ, độ phức tạp thời gian sẽ là O(2^N) gây tràn ngăn xếp và quá thời gian. Kỹ thuật Quy hoạch động (Dynamic Programming) lưu trữ kết quả của các bài toán con vào mảng để tính toán tuần tự trong O(N).

Yêu cầu

Tính giá trị F(N) bằng quy hoạch động 1D.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không truyền lời nhắc vào input(). Lời nhắc sẽ bị in vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 0 ≤ N ≤ 40.
• Thời gian chạy giới hạn: 1.0 giây.