Cấu trúc dữ liệu và Giải thuật Bài 55: Lập trình động Bottom-Up (Tabulation) - Tối ưu không gian và vòng lặp.

Ở Bài 54, chúng ta đã làm quen với Lập trình động theo trường phái Top-Down (Memoization): Bắt đầu từ bài toán lớn, dùng đệ quy bẻ nhỏ nó ra và lưu kết quả vào một bảng đệm (Map) để tránh tính toán trùng lặp.

Tuy nhiên, Top-Down vẫn mang trong mình một điểm yếu mang tính cấu trúc: Nó phụ thuộc vào Call Stack của hệ điều hành. Nếu bài toán yêu cầu độ sâu đệ quy quá lớn (ví dụ $N = 1,000,000$), hệ thống sẽ lập tức sụp đổ vì lỗi StackOverflow. Hơn nữa, việc tra cứu trên cấu trúc map gây tốn kém chu kỳ CPU do hiện tượng Cache Miss.

Để giải quyết triệt để vấn đề này, chúng ta bước sang chiến thuật đối lập hoàn toàn: Bottom-Up (Tabulation).

1. Tư duy từ Dưới lên (Tabulation)

Trái ngược với đệ quy, chiến thuật Bottom-Up hoạt động giống như một người thợ xây: Ta xây dựng nền móng trước, rồi mới chồng các tầng phía trên lên dần cho đến khi chạm tới đỉnh.

• Không dùng đệ quy, không dùng map.

• Chúng ta sử dụng một Mảng phẳng (Array/Slice) tuyến tính để lưu trữ kết quả của các bài toán con.

• Xuất phát từ các trường hợp cơ sở (Base cases) có sẵn, ta dùng một vòng lặp for đơn giản để tính toán tiến dần đến kết quả cần tìm.

2. Triển khai Bottom-Up Fibonacci bằng Golang

Hãy nhìn cách biến đổi bài toán tính số Fibonacci từ đệ quy phức tạp thành một vòng lặp tuyến tính cực kỳ thanh lịch và an toàn:

Go

package main

func fibBottomUp(n int) int {
    if n <= 1 {
        return n
    }

    // 1. Tạo bảng (Tabulation Table) chứa n + 1 phần tử
    dp := make([]int, n+1)

    // 2. Thiết lập giá trị cơ sở (Base cases)
    dp[0] = 0
    dp[1] = 1

    // 3. Xây dựng từ dưới lên bằng vòng lặp tuyến tính
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }

    // Trả về kết quả ở đỉnh của bảng
    return dp[n]
}

• Độ phức tạp thời gian: $O(n)$

• Độ phức tạp không gian: $O(n)$ do phải cấp phát mảng dp.

3. Đỉnh cao tối ưu: Thu hẹp không gian xuống $O(1)$

Nếu quan sát kỹ đoạn code trên, bạn sẽ nhận ra một chi tiết thú vị: Để tính ra giá trị tại bước i, thực chất chúng ta chỉ cần đúng 2 giá trị đứng ngay trước nó (dp[i-1] và dp[i-2]). Toàn bộ các giá trị tính từ 0 đến i-2 phía trước đều trở nên vô tác dụng.

Tại sao phải tốn RAM để lưu trữ cả một cái mảng dài dằng dặc trong khi ta chỉ cần giữ 2 biến trạng thái?

Chúng ta có thể bóp nghẹt không gian bộ nhớ xuống mức $O(1)$ tuyệt đối:

Go

func fibOptimized(n int) int {
    if n <= 1 {
        return n
    }

    prev2 := 0 // Tương ứng F(i-2)
    prev1 := 1 // Tương ứng F(i-1)
    current := 0

    for i := 2; i <= n; i++ {
        current = prev1 + prev2
        // Trượt cửa sổ dữ liệu
        prev2 = prev1
        prev1 = current
    }

    return current
}

Chiến thuật này được gọi là Space Optimization (Tối ưu không gian bằng con trỏ trượt). Nó biến một thuật toán tốn RAM thành một cỗ máy chạy băng băng chỉ với vài thanh ghi CPU.

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

Tư duy Tabulation và tối ưu không gian của Lập trình động xuất hiện ở khắp mọi ngóc ngách của phần mềm hiệu năng cao:

• Tính toán tồn kho và Dự báo chuỗi thời gian (E-commerce Supply Chain): Các hệ thống dự báo nhu cầu hàng hóa của Hasaki hay các bài toán tối ưu hóa đóng gói thùng hàng (Knapsack Problem) sử dụng bảng Tabulation nhiều chiều để tính toán lợi nhuận tối đa trong giới hạn trọng lượng cho phép của xe vận chuyển.

• Xử lý tài chính và Lãi suất kép: Các bảng tính toán biểu đồ tài chính dài hạn được dựng sẵn bằng mảng Bottom-Up để render giao diện tức thì cho người dùng mà không cần gọi lại các hàm tính toán phức tạp ở backend.

Lập trình động Bottom-Up khép lại chuỗi kỹ thuật cốt lõi của cấu trúc dữ liệu và giải thuật. Từ mảng tuyến tính cho đến đồ thị, cây, chuỗi ký tự và tối ưu trạng thái, việc nắm vững các mô hình này chính là tấm vé thông hành giúp Hiếu thiết kế nên những hệ thống backend vừa chạy nhanh như chớp, vừa tiết kiệm tài nguyên RAM tối đa.