Memoization và Tabulation khác nhau thế nào?

Memoization là top-down: viết recursion tự nhiên rồi cache kết quả của state đã tính.

• Dễ code khi state space phức tạp hoặc không phải state nào cũng được chạm tới.
• Tabulation là bottom-up: tạo bảng và tính từ base case lên đáp án.
• Thường kiểm soát memory tốt hơn và tránh stack overflow.

Ví dụ Fibonacci memo vẫn có recursion depth O(n), còn tabulation có thể tối ưu xuống hai biến.

• Trong interview, nếu cần nhanh và recurrence tự nhiên, bắt đầu với memo; sau đó nói cách chuyển sang tabulation/space optimized để thể hiện hiểu sâu.