Tại sao việc xác định sai Base Cases (Trường hợp cơ sở) lại dẫn đến lỗi tràn bộ nhớ hoặc kết quả sai lệch trong thuật toán Dynamic Programming, và các bước chuẩn hóa để thiết lập Base Cases an toàn là gì?

Question

Accepted Answer

Bản chất vấn đề
Base Cases (Trường hợp cơ sở) chính là mỏ neo dừng lại của đệ quy trong Top-Down hoặc là điểm khởi đầu của vòng lặp trong Bottom-Up. Nếu Base Cases bị thiết lập thiếu, sai giá trị khởi tạo hoặc thiếu điều kiện biên, chương trình sẽ rơi vào vòng lặp vô hạn (Infinite Recursion) dẫn đến lỗi Stack Overflow, hoặc trả về kết quả sai lệch nghiêm trọng do lan truyền giá trị rác.
Ví dụ thực tế
Xét bài toán tính số Fibonacci: F(n) = F(n-1) + F(n-2).

Base Cases đúng: F(0) = 0, F(1) = 1.
Lỗi phổ biến của Junior: Quên định nghĩa F(0), hoặc truyền vào tham số âm nhưng không có điều kiện chặn (if n < 0: return 0). Khi đó, hàm đệ quy sẽ gọi mãi mãi xuống các giá trị -1, -2, -3... cho đến khi cạn kiệt Stack.

Các bước chuẩn hóa thiết lập Base Cases

Xác định miền giá trị hợp lệ: Liệt kê tất cả các đầu vào nhỏ nhất có thể của bài toán mà không cần phải tính toán qua bài toán con.
Xử lý giá trị biên (Boundary Conditions): Đảm bảo các trường hợp 0, 1, hoặc các mảng/chuỗi có độ dài bằng 0 hoặc 1 được xử lý tường minh.
Kiểm tra tính an toàn của tham số: Luôn bổ sung điều kiện chặn cho các giá trị âm hoặc vượt quá giới hạn cho phép trước khi thực hiện State Transitions.
Kiểm tra tính đơn điệu: Đảm bảo kết quả của Base Cases khớp hoàn toàn với công thức truy hồi tổng quát khi áp dụng cho bước tiếp theo.

Tại sao việc xác định sai Base Cases (Trường hợp cơ sở) lại dẫn đến lỗi tràn bộ nhớ hoặc kết quả sai lệch trong thuật toán Dynamic Programming, và các bước chuẩn hóa để thiết lập Base Cases an toàn là gì?

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi dynamic programming liên quan cùng chủ đề