Cấu trúc dữ liệu và Giải thuật Bài 54: Nhập môn Lập trình động (Dynamic Programming) - Từ Đệ quy chồng chéo đến Ghi nhớ (Memoization).

Trong suốt 10 chương vừa qua, chúng ta đã đi qua các cấu trúc dữ liệu lưu trữ và tìm kiếm. Tuy nhiên, khi đối mặt với các bài toán tối ưu hóa — nơi hệ thống phải đưa ra quyết định tốt nhất trong hàng triệu phương án bùng nổ theo cấp số nhân — các thuật toán thông thường sẽ bó tay. Đó là lãnh địa của Lập trình động (Dynamic Programming - DP), ác mộng của mọi buổi phỏng vấn nhưng là vũ khí tối thượng của kỹ sư hệ thống.

1. Cạm bẫy của Đệ quy thuần túy và Bài toán Fibonacci

Để hiểu bản chất của DP, hãy xét bài toán tính số Fibonacci thứ $N$: F(n) = F(n-1) + F(n-2).

Nếu viết một hàm đệ quy ngây thơ:

• Khi tính F(5), hệ thống gọi F(4) và F(3).

• Để tính F(4), nó lại gọi F(3) và F(2).

• Hãy chú ý: F(3) bị tính lặp đi lặp lại nhiều lần một cách vô ích.

Hiện tượng này gọi là Đệ quy chồng chéo (Overlapping Subproblems). Khi $N$ lớn lên (ví dụ $N = 50$), số lần tính trùng lặp phình to thành hàng tỷ phép tính, đẩy độ phức tạp thời gian lên mức thảm họa $O(2^n)$, khiến CPU bị treo cứng.

2. Giải pháp Ghi nhớ (Memoization / Top-Down)

Lập trình động không phải là một phép màu toán học mới, nó thực chất là sự kết hợp tinh tế giữa Đệ quy và Bộ nhớ đệm (Memoization / Caching).

Quy luật vận hành rất thực tế: "Đừng bao giờ tính lại một bài toán mà bạn đã giải quyết trong quá khứ."

1. Trước khi tiến hành tính toán một giá trị F(n), hệ thống kiểm tra xem kết quả của nó đã được lưu trong một bảng tạm hoặc Map hay chưa.

2. Nếu đã có, trả về ngay lập tức với tốc độ $O(1)$.

3. Nếu chưa, tiến hành tính toán, sau đó lưu kết quả vào bảng trước khi trả về để các lời gọi sau tái sử dụng.

3. Hiện thực hóa Memoization bằng Golang

Go

package main

// Hàm tính Fibonacci tối ưu bằng Memoization (Top-Down DP)
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    
    // Kiểm tra xem đã tính toán trong quá khứ chưa
    if val, exists := memo[n]; exists {
        return val
    }
    
    // Tính toán và lưu vào Map trước khi trả về
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

func Fib(n int) int {
    memo := make(map[int]int)
    return fibMemo(n, memo)
}

Nhờ chiến thuật "nhớ bài", độ phức tạp thời gian từ mức thảm họa $O(2^n)$ đã rơi rụng xuống chỉ còn $O(n)$ tuyến tính hoàn hảo.

4. Ứng dụng trong Kiến trúc Hệ thống

Tư duy Memoization của Lập trình động chính là nền móng cho các giải pháp tối ưu hóa backend hiện đại:

• Application Caching (Redis / Memcached): Việc lưu trữ kết quả truy vấn database hoặc API đắt đỏ vào RAM để các request sau gọi lại chính là ứng dụng thực tế của bảng nhớ Memoization.

• Memoization Pattern trong Functional Programming: Nhiều ngôn ngữ lập trình hiện đại cung cấp sẵn cơ chế tự động cache kết quả hàm (Pure Functions) để tiết kiệm chu kỳ CPU.

Memoization giải quyết bài toán theo hướng từ trên xuống (Top-Down). Tuy nhiên, khi độ sâu của đệ quy quá lớn, Call Stack của hệ điều hành có thể bị tràn (StackOverflow). Để loại bỏ hoàn toàn đệ quy, chúng ta sẽ chuyển sang chiến thuật xây dựng từ dưới lên bằng bảng lặp.