Thư Viện Câu Hỏi Phỏng Vấn

Question

Hãy phân biệt sự khác nhau giữa tiếp cận Bottom-Up (Tabulation) và Top-Down (Memoization) trong Quy hoạch động?

Senior

Answer 1

Top-Down (Memoization): Bắt đầu giải quyết từ bài toán lớn nhất bằng đệ quy. Trong quá trình chạy, kết quả của các bài toán con sẽ được lưu lại (thường trong HashMap hoặc mảng). Khi gặp lại bài toán con đó, ta trả về ngay kết quả đã lưu mà không cần tính lại. Dễ hiểu và tự nhiên nhưng tốn chi phí gọi hàm đệ quy trên Stack.

Bottom-Up (Tabulation): Bắt đầu giải quyết từ các bài toán con nhỏ nhất trước, điền kết quả vào một bảng (mảng 1D hoặc 2D) bằng vòng lặp, sau đó sử dụng các kết quả này để tính toán dần lên bài toán lớn hơn. Tránh được việc tràn Stack và thường tối ưu hơn về không gian bộ nhớ.

Answer 2

Bài toán yêu cầu chọn các đồ vật có khối lượng và giá trị sao cho tổng khối lượng không vượt quá W và tổng giá trị lớn nhất:

Trạng thái: Gọi dp[i][w] là giá trị lớn nhất có thể đạt được khi chọn trong i đồ vật đầu tiên với giới hạn khối lượng là w.
Công thức truy hồi: Với đồ vật thứ i có khối lượng weight[i] và giá trị val[i]:
- Nếu weight[i] > w: Không thể chọn đồ vật này -> dp[i][w] = dp[i-1][w].
- Nếu weight[i] <= w: Ta chọn giá trị lớn hơn giữa việc lấy hoặc không lấy đồ vật -> dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + val[i]).
Kết quả: Nằm ở ô dp[n][W] với độ phức tạp thời gian là O(n*W).

Answer 3

Trong lập trình giải thuật với Dynamic Programming, việc làm chủ LCS & LIS yêu cầu lập trình viên hiểu rõ cấu trúc vật lý trong bộ nhớ và độ phức tạp tính toán:

Độ phức tạp: Luôn đánh giá Time Complexity (thời gian) và Space Complexity (không gian) tối ưu nhất (ví dụ: tối ưu từ O(n^2) xuống O(n log n)).
Trường hợp biên (Edge Cases): Xử lý kỹ các giá trị null, mảng rỗng, giá trị giới hạn cực đại/cực tiểu của kiểu dữ liệu.
Mã nguồn mẫu: Triển khai giải pháp rõ ràng, súc tích bằng các cấu trúc dữ liệu cơ bản, tránh lạm dụng bộ nhớ phụ khi không cần thiết.

Thư Viện Câu Hỏi Phỏng Vấn

Hãy phân biệt sự khác nhau giữa tiếp cận Bottom-Up (Tabulation) và Top-Down (Memoization) trong Quy hoạch động?

Bài toán cái túi (0/1 Knapsack Problem) được giải quyết bằng Quy hoạch động như thế nào?

Làm thế nào để triển khai và tối ưu hóa thuật toán hoặc cấu trúc dữ liệu liên quan đến LCS & LIS trong chủ đề Dynamic Programming?