Lập Trình Động: Chuyên Sâu & Tổng Kết (Dynamic Programming)

Chào mừng bạn đến với bài viết số 14 trong series về cấu trúc dữ liệu và giải thuật.

Hôm nay, chúng ta sẽ khám phá một kỹ thuật mạnh mẽ: Lập trình động (Dynamic Programming).

Đây là một công cụ không thể thiếu cho bất kỳ lập trình viên nào muốn giải quyết các bài toán phức tạp.

1. Giới Thiệu Về Lập Trình Động

Lập trình động (Dynamic Programming - DP) là một phương pháp giải quyết bài toán bằng cách chia nhỏ bài toán lớn thành các bài toán con nhỏ hơn.

Các bài toán con này được giải quyết một cách độc lập và kết quả của chúng được lưu trữ lại.

Khi gặp lại một bài toán con đã được giải trước đó, chúng ta chỉ cần lấy kết quả đã lưu thay vì tính toán lại từ đầu.

Điều này giúp tiết kiệm thời gian và tài nguyên tính toán đáng kể.

Nguyên tắc cốt lõi của DP là "ghi nhớ" (memoization) hoặc "bảng phương án" (tabulation).

Ghi nhớ (Memoization): Tiếp cận từ trên xuống (top-down). Giải quyết bài toán lớn bằng cách đệ quy, nhưng lưu trữ kết quả của các bài toán con để sử dụng lại.

Bảng phương án (Tabulation): Tiếp cận từ dưới lên (bottom-up). Giải quyết các bài toán con nhỏ nhất trước, sau đó sử dụng kết quả của chúng để xây dựng lời giải cho các bài toán lớn hơn.

DP thường được áp dụng cho các bài toán có tính chất overlapping subproblems (các bài toán con chồng chéo) và optimal substructure (cấu trúc con tối ưu).

Overlapping subproblems nghĩa là bài toán lớn được chia thành các bài toán con, và các bài toán con này lại chia thành các bài toán con nhỏ hơn, và có nhiều bài toán con bị trùng lặp.

Optimal substructure nghĩa là lời giải tối ưu cho bài toán lớn có thể được xây dựng từ các lời giải tối ưu của các bài toán con.

2. Ví Dụ Minh Họa: Bài Toán Fibonacci

Dãy Fibonacci là một ví dụ kinh điển để minh họa sức mạnh của DP.

Dãy này được định nghĩa như sau: F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) cho n > 1.

Nếu chúng ta tính toán F(n) bằng phương pháp đệ quy thông thường, chúng ta sẽ phải tính toán lại rất nhiều giá trị Fibonacci đã được tính trước đó.

Điều này dẫn đến độ phức tạp thời gian là O(2^n), rất chậm cho các giá trị n lớn.

Tuy nhiên, chúng ta có thể sử dụng DP để giải quyết bài toán này một cách hiệu quả hơn.

2.1. Fibonacci với Memoization (Ghi Nhớ)

Chúng ta sẽ sử dụng một mảng để lưu trữ các giá trị Fibonacci đã được tính toán.

Khi cần tính F(n), chúng ta sẽ kiểm tra xem giá trị này đã được lưu trữ trong mảng hay chưa.

Nếu đã có, chúng ta chỉ cần trả về giá trị đó. Nếu chưa, chúng ta sẽ tính toán và lưu trữ giá trị vào mảng.

import java.util.Arrays;

public class Fibonacci {

    public static int fibonacciMemoization(int n, int[] memo) {
        if (memo[n] != -1) {
            return memo[n];
        }
        if (n <= 1) {
            memo[n] = n;
            return n;
        }
        memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
        return memo[n];
    }

    public static int fibonacci(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fibonacciMemoization(n, memo);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
    }
}

Độ phức tạp thời gian của phương pháp này là O(n), vì chúng ta chỉ cần tính toán mỗi giá trị Fibonacci một lần.

2.2. Fibonacci với Tabulation (Bảng Phương Án)

Chúng ta sẽ xây dựng một mảng từ dưới lên, bắt đầu từ F(0) và F(1), sau đó tính toán các giá trị Fibonacci tiếp theo bằng cách sử dụng các giá trị đã được tính trước đó.

public class Fibonacci {

    public static int fibonacciTabulation(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci(" + n + ") = " + fibonacciTabulation(n));
    }
}

Độ phức tạp thời gian của phương pháp này cũng là O(n).

3. Ví Dụ Minh Họa: Bài Toán Cái Túi (Knapsack Problem)

Bài toán cái túi (Knapsack problem) là một bài toán tối ưu hóa kinh điển.

Chúng ta có một cái túi có trọng lượng tối đa là W và một danh sách các vật phẩm, mỗi vật phẩm có trọng lượng wi và giá trị vi.

Mục tiêu là chọn một tập hợp các vật phẩm để đặt vào túi sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất.

Chúng ta có thể sử dụng DP để giải quyết bài toán này.

Gọi dp[i][w] là giá trị lớn nhất có thể đạt được khi xem xét i vật phẩm đầu tiên và trọng lượng tối đa là w.

Công thức đệ quy cho dp[i][w] như sau:

• Nếu trọng lượng của vật phẩm thứ i (wi) lớn hơn w, thì dp[i][w] = dp[i-1][w] (chúng ta không thể đặt vật phẩm thứ i vào túi).
• Ngược lại, dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) (chúng ta chọn giá trị lớn nhất giữa việc không đặt vật phẩm thứ i vào túi và đặt vật phẩm thứ i vào túi).

public class Knapsack {

    public static int knapsack(int W, int[] wt, int[] val, int n) {
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] val = new int[] { 60, 100, 120 };
        int[] wt = new int[] { 10, 20, 30 };
        int W = 50;
        int n = val.length;
        System.out.println("Giá trị lớn nhất có thể đạt được = " + knapsack(W, wt, val, n));
    }
}

Độ phức tạp thời gian của phương pháp này là O(nW), trong đó n là số lượng vật phẩm và W là trọng lượng tối đa của túi.

4. Ưu Điểm và Nhược Điểm của Lập Trình Động

Ưu điểm:

• Giải quyết được các bài toán phức tạp một cách hiệu quả.
• Tiết kiệm thời gian và tài nguyên tính toán bằng cách lưu trữ và sử dụng lại kết quả của các bài toán con.

Nhược điểm:

• Đôi khi cần nhiều bộ nhớ để lưu trữ kết quả của các bài toán con.
• Có thể khó hiểu và khó triển khai đối với các bài toán phức tạp.

5. Kết Luận

Lập trình động là một kỹ thuật mạnh mẽ để giải quyết các bài toán tối ưu hóa và các bài toán có tính chất overlapping subproblems và optimal substructure.

Qua bài viết này, bạn đã được làm quen với khái niệm cơ bản của DP và hai ví dụ minh họa điển hình: bài toán Fibonacci và bài toán cái túi.

Hãy luyện tập thêm với nhiều bài toán khác nhau để nắm vững kỹ thuật này và áp dụng nó vào các dự án thực tế của bạn.

Hy vọng bài viết này hữu ích cho bạn. Chúc bạn thành công trên con đường chinh phục các thuật toán!