Giới thiệu về Quy hoạch động

Quy hoạch động (dynamic programming) là một mô hình thuật toán (algorithmic paradigm) quan trọng giúp chia nhỏ một bài toán thành một chuỗi các bài toán con (subproblem) và tránh tính toán thừa (redundant computation) bằng cách lưu trữ lời giải của các bài toán con, từ đó cải thiện đáng kể hiệu quả thời gian.

Trong phần này, chúng ta bắt đầu với một ví dụ kinh điển, trước hết trình bày lời giải bằng quay lui vét cạn (brute force backtracking), quan sát các bài toán con trùng lặp (overlapping subproblem) trong đó, rồi dần dần rút ra lời giải quy hoạch động hiệu quả hơn.

Leo cầu thang

Cho một cầu thang có \(n\) bậc, mỗi lần bạn có thể bước lên \(1\) hoặc \(2\) bậc. Hỏi có bao nhiêu cách khác nhau để leo lên đến đỉnh?

Như hình dưới đây, đối với cầu thang \(3\) bậc, có \(3\) cách khác nhau để leo lên đến đỉnh.

Mục tiêu của bài toán này là xác định số lượng cách đi, vì vậy chúng ta có thể cân nhắc sử dụng quay lui (backtracking) để liệt kê tất cả các khả năng. Cụ thể, hãy tưởng tượng việc leo cầu thang như một quy trình lựa chọn nhiều vòng: bắt đầu từ mặt đất, mỗi vòng chọn đi lên \(1\) hoặc \(2\) bậc, tăng biến đếm thêm \(1\) bất cứ khi nào đạt đến đỉnh cầu thang, và cắt nhánh khi vượt quá đỉnh. Mã nguồn như sau:

[file]{climbing_stairs_backtrack}-[class]{}-[func]{climbing_stairs_backtrack}

Phương pháp 1: Tìm kiếm vét cạn

Các thuật toán quay lui thường không phân tách bài toán một cách tường minh, mà coi việc giải quyết bài toán là một chuỗi các bước ra quyết định, tìm kiếm tất cả các lời giải khả thi thông qua thử và cắt nhánh.

Chúng ta có thể thử phân tích bài toán này từ góc độ phân tách bài toán. Gọi số cách để leo lên bậc thứ \(i\) là \(dp[i]\), khi đó \(dp[i]\) là bài toán gốc, và các bài toán con của nó bao gồm:

\[ dp[i-1], dp[i-2], \dots, dp[2], dp[1] \]

Vì mỗi vòng chúng ta chỉ có thể đi lên \(1\) hoặc \(2\) bậc, nên khi đứng ở bậc thứ \(i\), chúng ta chỉ có thể đứng ở bậc thứ \(i-1\) hoặc \(i-2\) ở vòng trước đó. Nói cách khác, chúng ta chỉ có thể đi tới bậc thứ \(i\) từ bậc thứ \(i-1\) hoặc \(i-2\).

Điều này dẫn đến một kết luận quan trọng: số cách leo lên bậc thứ \(i-1\) cộng với số cách leo lên bậc thứ \(i-2\) bằng số cách leo lên bậc thứ \(i\). Công thức như sau:

\[ dp[i] = dp[i-1] + dp[i-2] \]

Điều này có nghĩa là trong bài toán leo cầu thang, tồn tại một hệ thức truy hồi (recurrence relation) giữa các bài toán con, và lời giải của bài toán gốc có thể được xây dựng từ lời giải của các bài toán con. Hình dưới đây minh họa hệ thức truy hồi này.

Chúng ta có thể thu được một lời giải tìm kiếm vét cạn dựa trên công thức truy hồi. Bắt đầu từ \(dp[n]\), phân tách đệ quy một bài toán lớn hơn thành tổng của hai bài toán nhỏ hơn, cho đến khi đạt đến các bài toán con nhỏ nhất là \(dp[1]\) và \(dp[2]\) rồi quay về. Trong đó, lời giải cho các bài toán con nhỏ nhất đã biết trước, cụ thể là \(dp[1] = 1\) và \(dp[2] = 2\), lần lượt đại diện cho \(1\) và \(2\) cách để leo lên các bậc thứ \(1\) và thứ \(2\).

Quan sát mã nguồn sau: giống như mã nguồn quay lui tiêu chuẩn, nó cũng sử dụng tìm kiếm theo chiều sâu (depth-first search) nhưng ngắn gọn hơn:

[file]{climbing_stairs_dfs}-[class]{}-[func]{climbing_stairs_dfs}

Hình dưới đây cho thấy cây đệ quy (recursion tree) được tạo ra bởi tìm kiếm vét cạn. Đối với bài toán \(dp[n]\), độ sâu của cây đệ quy của nó là \(n\), với độ phức tạp thời gian là \(O(2^n)\). Sự tăng trưởng lũy thừa là bùng nổ; nếu nhập vào một giá trị \(n\) tương đối lớn, thời gian chờ đợi có thể rất lâu.

Quan sát hình trên, độ phức tạp thời gian lũy thừa là do "các bài toán con trùng lặp" gây ra. Ví dụ, \(dp[9]\) được phân tách thành \(dp[8]\) và \(dp[7]\), còn \(dp[8]\) được phân tách thành \(dp[7]\) và \(dp[6]\), cả hai đều chứa bài toán con \(dp[7]\).

Và cứ tiếp tục như vậy, các bài toán con chứa các bài toán con trùng lặp nhỏ hơn, kéo dài vô tận. Phần lớn tài nguyên tính toán bị lãng phí vào các bài toán con trùng lặp này.

Phương pháp 2: Đệ quy có nhớ

Để nâng cao hiệu quả thuật toán, chúng ta muốn tất cả các bài toán con trùng lặp chỉ được tính toán một lần. Để làm việc này, chúng ta khai báo một mảng mem để ghi lại lời giải của từng bài toán con và cắt nhánh các bài toán con trùng lặp trong quá trình tìm kiếm.

1. Khi tính toán \(dp[i]\) lần đầu tiên, chúng ta ghi nhận nó vào mem[i] để sử dụng sau.
2. Khi cần tính toán lại \(dp[i]\), chúng ta có thể trực tiếp lấy kết quả từ mem[i], từ đó tránh việc tính toán trùng lặp cho bài toán con đó.

Mã nguồn như sau:

[file]{climbing_stairs_dfs_mem}-[class]{}-[func]{climbing_stairs_dfs_mem}

Quan sát hình dưới đây: sau khi sử dụng đệ quy có nhớ (memoization), tất cả các bài toán con trùng lặp chỉ cần tính toán một lần, giúp giảm độ phức tạp thời gian xuống còn \(O(n)\), đây là một bước nhảy vọt to lớn.

Phương pháp 3: Quy hoạch động

Đệ quy có nhớ là một phương pháp từ trên xuống (top-down): chúng ta bắt đầu từ bài toán gốc (nút gốc), phân tách đệ quy các bài toán con lớn hơn thành các bài toán nhỏ hơn, cho đến khi đạt đến các bài toán con nhỏ nhất đã biết (nút lá). Sau đó, bằng cách quay lui, chúng ta thu thập lời giải của các bài toán con theo từng lớp để xây dựng lời giải của bài toán gốc.

Ngược lại, quy hoạch động là một phương pháp từ dưới lên (bottom-up): bắt đầu từ lời giải của các bài toán con nhỏ nhất, xây dựng lặp đi lặp lại lời giải cho các bài toán con lớn hơn cho đến khi có được lời giải của bài toán gốc.

Vì quy hoạch động không bao gồm quá trình quay lui, nó chỉ yêu cầu vòng lặp để triển khai mà không cần đệ quy. Trong mã nguồn sau, chúng ta khởi tạo một mảng dp để lưu trữ lời giải của các bài toán con, đóng vai trò ghi nhớ tương tự như mảng mem trong đệ quy có nhớ:

[file]{climbing_stairs_dp}-[class]{}-[func]{climbing_stairs_dp}

Hình dưới đây mô phỏng quá trình thực thi của mã nguồn trên.

Giống như thuật toán quay lui, quy hoạch động cũng sử dụng khái niệm trạng thái (state) để đại diện cho các giai đoạn cụ thể của việc giải quyết vấn đề, với mỗi trạng thái tương ứng với một bài toán con và lời giải tối ưu cục bộ tương ứng của nó. Ví dụ, trạng thái trong bài toán leo cầu thang được định nghĩa là số bậc thang hiện tại \(i\).

Dựa trên nội dung trên, chúng ta có thể tóm tắt các thuật ngữ thường dùng trong quy hoạch động.

• Mảng dp được gọi là bảng dp (dp table), trong đó \(dp[i]\) đại diện cho lời giải của bài toán con tương ứng với trạng thái \(i\).
• Các trạng thái tương ứng với các bài toán con nhỏ nhất (bậc thứ \(1\) và thứ \(2\)) được gọi là trạng thái ban đầu (initial state).
• Công thức truy hồi \(dp[i] = dp[i-1] + dp[i-2]\) được gọi là phương trình chuyển trạng thái (state transition equation).

Tối ưu hóa không gian

Những độc giả tinh ý có thể đã nhận thấy rằng vì \(dp[i]\) chỉ liên quan đến \(dp[i-1]\) và \(dp[i-2]\), nên chúng ta không cần sử dụng mảng dp để lưu trữ lời giải của tất cả các bài toán con, mà thay vào đó có thể sử dụng hai biến cuộn tịnh tiến. Mã nguồn như sau:

[file]{climbing_stairs_dp}-[class]{}-[func]{climbing_stairs_dp_comp}

Như mã nguồn trên cho thấy, bằng cách loại bỏ không gian bị chiếm dụng bởi mảng dp, độ phức tạp không gian được giảm từ \(O(n)\) xuống \(O(1)\).

Trong các bài toán quy hoạch động, trạng thái hiện tại thường chỉ phụ thuộc vào một số lượng giới hạn các trạng thái đi trước, cho phép chúng ta chỉ giữ lại các trạng thái cần thiết và tiết kiệm không gian bộ nhớ thông qua giảm chiều. Kỹ thuật tối ưu hóa không gian này được gọi là "biến cuộn" hoặc mảng cuộn (rolling array).