Cơ bản về lập trình động

5.1 Định nghĩa lập trình động.

Lập trình động (Dynamic Programming, DP) — là một phương pháp tối ưu hóa, được sử dụng để giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Lập trình động hiệu quả cho các bài toán có thể chia thành các bài toán con chồng lấn với cấu trúc tối ưu.

Nguyên tắc hoạt động:

1. Cấu trúc tối ưu:

Bài toán có cấu trúc tối ưu nếu giải pháp tối ưu của nó có thể được xây dựng từ những giải pháp tối ưu của các bài toán con. Điều này có nghĩa là có thể giải quyết bài toán lớn bằng cách giải quyết một số bài toán con nhỏ hơn.

2. Các bài toán con chồng lấn:

Bài toán có các bài toán con chồng lấn nếu các bài toán con của nó được lặp lại nhiều lần trong quá trình giải quyết bài toán. Lập trình động giải quyết hiệu quả các bài toán với bài toán con chồng lấn bằng cách lưu trữ kết quả của các bài toán con đã được giải (memoization).

3. Memoization và Tabulation:

Memoization (từ trên xuống): Phương pháp đệ quy, trong đó kết quả của các bài toán con được lưu trữ trong bộ nhớ để tránh tính toán lại.

Tabulation (từ dưới lên): Phương pháp lặp, trong đó kết quả của các bài toán con được tính toán và lưu trữ trong bảng (thường là mảng) và được sử dụng để tính toán kết quả cuối cùng.

Ví dụ về các bài toán được giải quyết bằng phương pháp lập trình động

5.2 Bài toán ba lô.

Bài toán:

Có một bộ các vật phẩm, mỗi cái có trọng lượng và giá trị. Cần chọn các vật phẩm cho ba lô với khả năng chứa giới hạn, để tối đa hóa tổng giá trị.

Quan trọng! Không giống như bài toán tương tự, có thể giải quyết tốt bằng thuật toán tham lam, trong bài toán này không thể chia nhỏ các vật phẩm.

Giải pháp:

Tạo một bảng, trong đó các hàng tương ứng với các vật phẩm, và các cột là khả năng chứa của ba lô có thể có. Giá trị trong ô đại diện cho giá trị tối đa cho số lượng vật phẩm và khả năng chứa đó.

Độ phức tạp thời gian: O(n * W), trong đó n là số lượng vật phẩm, W là khả năng chứa của ba lô.

Ví dụ mã Python:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 Bài toán tìm đường ngắn nhất

Bài toán:

Tìm các đường ngắn nhất giữa tất cả các cặp đỉnh của đồ thị có trọng số.

Giải pháp:

Sử dụng một bảng, trong đó các hàng và cột tương ứng với các đỉnh của đồ thị. Giá trị trong ô đại diện cho khoảng cách ngắn nhất giữa hai đỉnh.

Độ phức tạp thời gian: O(V^3), trong đó V là số lượng đỉnh

Ví dụ mã Python:

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 So sánh lập trình động với các phương pháp khác.

So sánh với phương pháp brute force:

Độ phức tạp thời gian:

• Brute force: thường có độ phức tạp thời gian theo hàm mũ (ví dụ, O(2^n) cho bài toán Fibonacci).
• Lập trình động: giảm độ phức tạp thời gian xuống thành hàm đa thức (ví dụ, O(n) cho bài toán Fibonacci).

Độ phức tạp không gian:

• Brute force: có thể sử dụng ít bộ nhớ hơn, nhưng chi phí thời gian cao.
• Lập trình động: có thể sử dụng thêm bộ nhớ để lưu trữ kết quả trung gian (ví dụ, O(n) cho bài toán Fibonacci với memoization), nhưng tiết kiệm thời gian.

So sánh với phương pháp greedy algorithms:

Tính tối ưu:

• Thuật toán tham lam: không phải lúc nào cũng tìm thấy giải pháp tối ưu toàn cục, nhưng hoạt động nhanh hơn và đơn giản trong việc triển khai.
• Lập trình động: luôn tìm thấy giải pháp tối ưu toàn cục, nhưng yêu cầu nhiều tài nguyên tính toán hơn.

Ví dụ bài toán:

• Thuật toán tham lam: bài toán ba lô với phân đoạn (fractional knapsack), cây khung tối thiểu (MST).
• Lập trình động: bài toán ba lô (nguyên), chuỗi con chung dài nhất (LCS).