Dynamic Programming
Memoization, recursion & DP — breaking problems into subproblems
Dynamic programming (DP) solves a hard problem by breaking it into overlapping subproblems and reusing their answers instead of recomputing them.
When does DP apply?
Two properties make a problem a DP candidate: optimal substructure (the best overall answer is built from best sub-answers) and overlapping subproblems (the same sub-answer is needed many times). The Fibonacci sequence is the textbook example — naive recursion recomputes the same values exponentially, while caching them makes it linear.
Top-down vs bottom-up
Memoization (top-down) keeps the natural recursion but caches each result the first time it is computed. Tabulation (bottom-up) fills a table from the smallest subproblems upward, often saving stack space. Both turn exponential work into polynomial work.
Recursion & backtracking
Classic teaching examples — the knapsack problem, the Tower of Hanoi and the N-Queens puzzle — show how recursion, memoization and backtracking relate. Step through them below to watch the recursion tree collapse once results are cached.
Try it interactively
Trình trực quan hóa Knapsack 0/1
Quy hoạch động (dynamic programming) cho bài toán knapsack 0/1 dạng hoạt họa — điền bảng DP từng ô một, làm nổi bật các ô phụ thuộc, có điều khiển từng bước. Chạy ngay trong trình duyệt.
Mở công cụTrình trực quan hóa dãy Fibonacci
Dãy Fibonacci được minh họa động — mỗi số hạng là tổng của hai số hạng trước đó, dựng dần từng bước với các nút điều khiển. Chạy ngay trong trình duyệt.
Mở công cụTrình mô phỏng Tháp Hà Nội
Công cụ mô phỏng đệ quy giải bài toán Tháp Hà Nội — di chuyển các đĩa trong số bước tối thiểu 2ⁿ−1, có điều khiển từng bước. Chạy ngay trên trình duyệt.
Mở công cụTrình mô phỏng N-Queens
Mô phỏng động thuật toán quay lui (backtracking) cho bài toán N-Queens trên bàn cờ — thử, đặt quân, phát hiện xung đột và quay lui với các nút điều khiển từng bước. Chạy ngay trên trình duyệt.
Mở công cụCâu hỏi thường gặp
Bài toán N-Queens là gì?
Đặt n quân hậu lên bàn cờ n×n sao cho không có hai quân nào tấn công lẫn nhau — không chung hàng, không chung cột và không chung đường chéo.
Backtracking giải bài toán này như thế nào?
Đặt quân hậu lần lượt theo từng cột. Với mỗi cột, thử từng hàng; nếu vị trí an toàn thì đệ quy sang cột tiếp theo; nếu không hàng nào an toàn thì quay lui và thử một hàng khác ở cột trước đó.
Độ phức tạp thời gian của thuật toán là bao nhiêu?
Trường hợp xấu nhất xấp xỉ O(n!), nhưng việc cắt tỉa các vị trí xung đột giúp tìm ra một lời giải nhanh hơn nhiều trong thực tế.
Với giá trị n nào thì tồn tại lời giải?
Lời giải tồn tại với mọi n ngoại trừ 2 và 3. Bài toán 8-quân hậu kinh điển có 92 lời giải khác nhau.