Làm Chủ Quy Hoạch Động: Các Khuôn Mẫu Thường Gặp (Phần 1)

Xin chào anh em, lại là tôi - Jim đây!

Ở bài viết trước, chúng ta đã cùng nhau xây dựng nền móng với Khung Tư Duy 3 Bước, áp dụng nó để giải quyết các bài toán kinh điển. Đó là những viên gạch cực kỳ quan trọng, và giờ là lúc chúng ta dùng chúng để xây nên những công trình vĩ đại hơn.

Anh em nào chưa đọc bài nhập môn Quy hoạch động thì hãy đọc bài đó để nắm được Khung Tư Duy 3 Bước đã nhé: Nhập Môn Quy Hoạch Động Cơ Bản

Hôm nay, chúng ta sẽ thực hiện một bước nhảy vọt trong tư duy: Chuyển từ việc áp dụng công thức có sẵn sang việc tự mình nhận diện các cấu trúc tiềm ẩn và thiết kế lời giải. Để làm được điều này, chúng ta cần một kỹ năng mới đó là khả năng nhận dạng Pattern (khuôn mẫu).

Rất nhiều bài toán DP, dù có đề bài khác nhau, lại cùng chung một bộ xương logic. Nhiệm vụ của chúng ta là rèn luyện một đôi mắt tinh tường để nhìn qua lớp vỏ ngôn từ và nhận ra bộ xương quen thuộc bên trong.

Hãy cùng tôi bắt đầu nghiên cứu 2 trong số những patterns phổ biến của kỹ thuật này nhé!

1. Pattern #1: Lựa Chọn Vô Hạn (Unbounded Choice)

1.1. Làm sao để nhận ra?

Làm thế nào để biết một bài toán thuộc họ hàng nhà Cái Túi (Knapsack), và cụ thể hơn là loại lựa chọn vô hạn (Unbounded Knapsack)? Câu trả lời nằm ở việc nhận diện các dấu hiệu đặc trưng.

Dấu hiệu từ đề bài

Hãy như một thám tử và tìm kiếm những manh mối trong đề bài. Những từ này thường là tín hiệu rõ ràng nhất:

• "vô hạn"
• "dùng lặp lại"
• "mỗi loại có số lượng không giới hạn"
• "có thể chọn một món đồ nhiều lần"

Bất cứ khi nào anh em thấy những cụm từ này, đèn hiệu Unbounded Knapsack nên bật sáng trong đầu.

Câu hỏi tự vấn

Nếu đề bài không dùng từ ngữ rõ ràng, hãy tự đặt cho mình câu hỏi then chốt này:

"Khi tôi quyết định chọn một vật nào đó, tôi có được phép chọn lại chính vật đó ở các bước tiếp theo không?"

Nếu câu trả lời là Có, anh em đang đối mặt với một bài toán có tính chất lựa chọn không giới hạn.

Các lớp ngụy trang phổ biến

Đây mới là phần thú vị nhất. Unbounded Knapsack thường không xuất hiện dưới dạng một cái túi mà ẩn mình trong các bài toán khác.

• Bài toán Đổi Tiền (Coin Change): Cho các mệnh giá tiền và một số tiền S. Tìm số cách/số đồng xu ít nhất để tạo ra tổng S.
  • Phân tích: Mỗi mệnh giá tiền là một "vật". Giá trị mệnh giá là "trọng lượng". Tổng S là "sức chứa túi". Vì anh em có thể dùng một mệnh giá (ví dụ: đồng 5 nghìn) bao nhiêu lần tùy thích, đây chính là Unbounded Knapsack.
• Bài toán Cắt Thanh Sắt (Rod Cutting): Cho một thanh sắt dài N và bảng giá cho các đoạn cắt. Tìm cách cắt để tổng giá trị thu được là lớn nhất.
  • Phân tích: Chiều dài N của thanh sắt là "sức chứa túi". Các đoạn cắt có thể có (dài 1, 2,...) là các "loại vật". Độ dài đoạn cắt là "trọng lượng" và giá bán là "giá trị". Vì anh em có thể cắt nhiều đoạn có cùng độ dài k, đây cũng là Unbounded Knapsack.

1.2. Tư duy giải bài toán Unbounded Knapsack

Hãy cùng nhau phân tích bài toán gốc để nắm vững tư duy giải quyết nhé. Anh em hãy tưởng tượng mình là một tên trộm thông minh, đứng trước một kho báu vô tận và cần lấp đầy chiếc túi của mình sao cho thật giá trị.

Đề bài: Một tên trộm có N loại đồ vật. Loại thứ i có trọng lượng là w[i] và giá trị là v[i]. Tên trộm mang một cái túi có sức chứa tối đa là W. Mỗi loại đồ vật có số lượng vô hạn. Làm thế nào để chọn đồ vật sao cho tổng giá trị là lớn nhất mà không làm rách túi?

Chúng ta sẽ áp dụng Khung Tư Duy 3 Bước một cách chi tiết:

1. Xác định trạng thái:

   • Chúng ta cần đưa ra quyết định cho từng món đồ, và quyết định này phụ thuộc vào món đồ đang xét và sức chứa còn lại của túi.
   • Vì vậy, trạng thái của chúng ta sẽ là: dp[i][j] = tổng giá trị LỚN NHẤT có thể đạt được khi được phép lựa chọn trong i loại vật phẩm đầu tiên (từ 1 đến i) với một cái túi có sức chứa là j.

2. Xác định kết quả:

   • Mục tiêu cuối cùng là tìm giá trị lớn nhất khi đã xem xét tất cả N loại vật phẩm với sức chứa tối đa của túi là W.
   • Kết quả chính là dp[N][W].

3. Xác định công thức truy hồi:

   • Bây giờ, hãy tập trung vào cách tính dp[i][j]. Khi đứng trước vật phẩm loại i và túi có sức chứa j, tên trộm thông minh sẽ suy nghĩ: "Mình có nên lấy vật phẩm này không nhỉ?".

   • Có hai khả năng xảy ra:

     • Lựa chọn 1: KHÔNG lấy vật phẩm loại i

       • Lý do: Có thể vì vật i quá nặng (w[i] > j) hoặc đơn giản là ta không thích lấy nó.
       • Kết quả: Nếu không lấy vật i, thì giá trị tối ưu với i vật và sức chứa j cũng chính là giá trị tối ưu khi chỉ xét i-1 vật với cùng sức chứa j.
       • $\Rightarrow$ Giá trị trong trường hợp này là dp[i-1][j].

     • Lựa chọn 2: CÓ lấy vật phẩm loại i

       • Điều kiện: Ta chỉ có thể lấy nếu túi còn đủ chỗ, tức là w[i] <= j.
       • Tư duy khác biệt: Đây là điểm mấu chốt của Unbounded Knapsack. Sau khi bạn lấy 1 vật loại i, vì số lượng là vô hạn, bạn vẫn có thể tiếp tục lấy vật loại i nữa.
       • Kết quả:
         1. Bạn nhận được giá trị v[i].
         2. Sức chứa túi giảm xuống còn j - w[i].
         3. Bài toán còn lại là: Tìm giá trị tối ưu cho chiếc túi sức chứa j - w[i] và bạn vẫn được quyền chọn trong i vật phẩm đầu tiên (vì bạn vẫn có thể chọn lại vật i). Lời giải cho bài toán con này chính là dp[i][j - w[i]].
       • $\Rightarrow$ Tổng giá trị trong trường hợp này là v[i] + dp[i][j - w[i]].

   • Tổng hợp lại: Là một tên trộm tham lam, bạn sẽ chọn phương án nào cho giá trị lớn hơn. dp[i][j] = max( dp[i-1][j] , v[i] + dp[i][j - w[i]] ) (Không lấy vật i) , (Lấy vật i)

   • Base Case (Điểm khởi đầu):

     • dp[0][j] = 0: Nếu không có vật phẩm nào để chọn, giá trị luôn bằng 0.
     • dp[i][0] = 0: Nếu túi không có sức chứa, ta không thể bỏ gì vào, giá trị cũng bằng 0.

1.3. Mẹo tối ưu hóa

Khi nhìn vào công thức truy hồi của cả hai bài toán Knapsack, anh em sẽ thấy để tính toán trang thái i (kết quả khi xét đến vật i), chúng ta chỉ cần dữ liệu từ trạng thái i-1. Điều này gợi ý một cách tối ưu không gian lưu trữ cực kỳ hiệu quả: thay vì dùng một bảng 2D O(N*W), ta chỉ cần một mảng 1D O(W).

Tuy nhiên, cách chúng ta duyệt vòng lặp trên mảng 1D này lại quyết định chúng ta đang giải bài toán nào. Đây là một trong những vẻ đẹp tinh tế nhất của Quy Hoạch Động.

Hãy cùng phân tích thật kỹ tại sao lại có sự khác biệt này.

Phân tích bài toán 0/1 Knapsack (Mỗi vật chỉ lấy 1 lần)

• Công thức truy hồi: dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j - w[i]])
• Điểm cốt lõi: Để tính dp[i][j], cả hai lựa chọn (lấy hoặc không lấy) đều phụ thuộc vào kết quả của trạng thái TRƯỚC ĐÓ (i-1).
• Thử nghiệm với vòng lặp TIẾN (Forward):
  • Giả sử ta dùng mảng 1D dp[j] và duyệt j từ w[i] đến W.
  • Khi ta tính dp[5] cho vật i (với w[i]=2), công thức cần giá trị dp[5-2], tức dp[3].
  • Nhưng vì ta đang lặp tiến, giá trị dp[3] đã được tính toán và cập nhật cho vật i rồi ở bước j=3 trước đó.
  • Lúc này, ta đang vô tình dùng dp[i][3] để tính dp[i][5]. Điều này vi phạm công thức gốc, vì nó tương đương với việc bạn lấy vật i một lần ở j=3 và có thể lấy thêm một lần nữa ở j=5. Đây là logic của bài toán Unbounded, không phải 0/1 $\Rightarrow$ Cách này SAI.
• Giải pháp với vòng lặp NGƯỢC (Backward):
  • Bây giờ, hãy duyệt j từ W ngược về w[i].
  • Khi ta tính dp[5] cho vật i (với w[i]=2), công thức vẫn cần giá trị dp[3].
  • Vì ta lặp ngược, dp[3] chưa hề bị đụng đến trong vòng lặp của vật i này. Nó vẫn đang lưu giá trị tối ưu của i-1 vật.
  • Điều này đảm bảo rằng chúng ta đang truy cập đúng giá trị dp[i-1][3] như công thức gốc yêu cầu $\Rightarrow$ Cách này ĐÚNG.

Tóm lại cho 0/1 Knapsack: Vòng lặp ngược đảm bảo rằng khi bạn quyết định "lấy" một vật, bạn đang dựa trên kết quả của việc chưa hề có sự tồn tại của vật đó.

Phân tích bài toán Unbounded Knapsack (Lấy vật vô hạn lần)

• Công thức truy hồi: dp[i][j] = max(dp[i-1][j], v[i] + dp[i][j - w[i]])
• Điểm cốt lõi: Chú ý sự khác biệt, lựa chọn "lấy" vật i phụ thuộc vào dp[i][j - w[i]], tức là một kết quả khác cũng nằm ở trạng thái HIỆN TẠI (i). Điều này thể hiện logic "sau khi lấy vật i, ta vẫn có thể lấy tiếp chính nó".
• Giải pháp với vòng lặp TIẾN (Forward):
  • Bây giờ, vòng lặp tiến lại trở thành vũ khí hoàn hảo.
  • Khi ta tính dp[5] cho vật i (với w[i]=2), công thức cần giá trị dp[3].
  • Vì ta lặp tiến, dp[3] đã được cập nhật trong vòng lặp của vật i. Nó đang chứa giá trị dp[i][3] - giá trị tối ưu cho sức chứa 3 đã bao gồm khả năng lấy vật i.
  • Đây chính xác là những gì công thức v[i] + dp[i][j - w[i]] cần. Vòng lặp tiến mô phỏng một cách tự nhiên việc cập nhật liên tiếp trên cùng một vật phẩm $\Rightarrow$ Cách này ĐÚNG.

Tóm lại cho Unbounded Knapsack: Vòng lặp tiến cho phép giá trị của một vật phẩm ảnh hưởng ngay lập tức đến các kết quả sau trong cùng một lượt xét, mô phỏng hoàn hảo việc "chọn lại" một món đồ.

1.4. Code tham khảo (Tối ưu không gian)

#include <bits/stdc++.h>
using namespace std; int main()
{ ios_base::sync_with_stdio(false); cin.tie(NULL); int numItems, maxWeight; cin >> numItems >> maxWeight; vector<int> weights(numItems), values(numItems); for (int i = 0; i < numItems; ++i) cin >> weights[i] >> values[i]; // dp[j] là giá trị lớn nhất có thể đạt được với sức chứa túi là j. vector<long long> dp(maxWeight + 1, 0); // Duyệt qua từng loại vật phẩm for (int i = 0; i < numItems; ++i) { // Vòng lặp j chạy TIẾN (forward). Đây là điểm khác biệt mấu chốt. for (int j = weights[i]; j <= maxWeight; ++j) { // dp[j] ở vế phải là giá trị từ vòng lặp trước (tương đương dp[i-1][j]) // dp[j - weights[i]] là giá trị MỚI, đã được cập nhật ở vòng lặp i này // (tương đương dp[i][j - weights[i]]) dp[j] = max(dp[j], (long long)values[i] + dp[j - weights[i]]); } } cout << dp[maxWeight]; return 0;
}

2. Pattern #2: DP Trên Chuỗi (DP on Sequences)

2.1. Làm sao để nhận ra?

Một lớp bài toán DP cực lớn khác liên quan đến chuỗi.

Dấu hiệu từ đề bài

Các bài toán này thường xoay quanh việc so sánh, biến đổi, hoặc tìm thuộc tính chung giữa hai chuỗi. Hãy để ý các từ khóa:

• "biến đổi xâu A thành xâu B"
• "chi phí tối thiểu", "số phép toán ít nhất"
• "xâu con chung dài nhất"
• "xâu đối xứng" (palindrome)

Cấu trúc trạng thái kinh điển

Điểm chung của hầu hết các bài toán này là chúng đều có thể được giải quyết bằng một bảng DP 2 chiều. Trạng thái DP gần như luôn có dạng:

dp[i][j]: đại diện cho lời giải của bài toán con khi xét trên hai tiền tố: string2[1...i] (i ký tự đầu tiên của xâu string1) và string2[1...j] (j ký tự đầu tiên của xâu string2).

Hai bài toán tổ tiên của pattern này là Edit Distance và Xâu Con Chung Dài Nhất (LCS).

2.2. Tư duy giải bài toán Edit Distance

Đây là một ví dụ hoàn hảo và cực kỳ phổ biến để anh em luyện tư duy DP trên chuỗi.

Đề bài: Cho hai xâu A và B. Tìm số phép toán tối thiểu để biến đổi xâu A thành xâu B. Ba phép toán được cho phép là: Chèn, Xóa, Thay thế. Mỗi phép toán có chi phí là 1.

Ví dụ: biến "horse" thành "ros".

Chúng ta lại dùng Khung Tư Duy 3 Bước:

1. Xác định trạng thái:

   • Bài toán yêu cầu so sánh và biến đổi 2 chuỗi. Một cách tự nhiên, trạng thái của chúng ta sẽ phụ thuộc vào các phần của cả hai chuỗi.
   • dp[i][j] = chi phí TỐI THIỂU để biến đổi i ký tự đầu của xâu A (A[1...i]) thành j ký tự đầu của xâu B (B[1...j]).

2. Xác định kết quả:

   • Mục tiêu cuối cùng là biến đổi toàn bộ xâu A (dài m) thành toàn bộ xâu B (dài n).
   • Kết quả chính là dp[m][n].

3. Xác định công thức truy hồi (Cùng suy luận từng bước nhé!):

   • Để tính dp[i][j], chúng ta hãy tập trung vào 2 ký tự cuối cùng của 2 tiền tố đang xét: A[i-1] và B[j-1] (lưu ý chỉ số mảng bắt đầu từ 0).

   • Có hai tình huống lớn:

     • Tình huống 1: Hai ký tự cuối GIỐNG NHAU (A[i-1] == B[j-1])

       • Tư duy: Tuyệt! Ký tự cuối cùng đã khớp nhau do đó ta không cần tốn bất kỳ phép toán nào cho chúng.
       • Hành động: Bỏ qua hai ký tự này và giải quyết phần còn lại của bài toán.
       • Bài toán con: Chi phí để biến A[1...i] thành B[1...j] bây giờ chính bằng chi phí để biến A[1...i-1] thành B[1...j-1].
       • => dp[i][j] = dp[i-1][j-1]

     • Tình huống 2: Hai ký tự cuối KHÁC NHAU (A[i-1] != B[j-1])

       • Tư duy: Vì chúng khác nhau, ta bắt buộc phải thực hiện một phép toán để xử lý sự khác biệt này. Chúng ta có 3 cách, và ta sẽ chọn cách nào có tổng chi phí cuối cùng là nhỏ nhất.
       • Cách 1: Thay thế (Replace)
         • Mục tiêu: Biến A[i-1] thành B[j-1].
         • Hành động: Tốn 1 phép thay thế. Sau khi thay thế, hai ký tự cuối đã khớp. Bài toán còn lại là biến A[1...i-1] thành B[1...j-1].
         • Tổng chi phí: 1 + dp[i-1][j-1]
       • Cách 2: Xóa (Delete)
         • Mục tiêu: Biến A[1...i] thành B[1...j].
         • Hành động: Ta có thể nghĩ rằng ký tự A[i-1] là "thừa". Hãy xóa nó đi. Tốn 1 phép xóa. Sau khi xóa, ta cần biến chuỗi A[1...i-1] (ngắn hơn) thành chuỗi B[1...j].
         • Tổng chi phí: 1 + dp[i-1][j]
       • Cách 3: Chèn (Insert)
         • Mục tiêu: Biến A[1...i] thành B[1...j].
         • Hành động: Ta có thể nghĩ rằng chuỗi A đang "thiếu" ký tự B[j-1] ở cuối. Hãy chèn nó vào. Tốn 1 phép chèn. Sau khi chèn, ta chỉ cần lo biến chuỗi A[1...i] ban đầu thành chuỗi B[1...j-1] (ngắn hơn).
         • Tổng chi phí: 1 + dp[i][j-1]
       • Kết luận: Ta sẽ chọn cách có chi phí thấp nhất trong 3 cách trên.
       • => dp[i][j] = 1 + min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] ) (Replace) , (Delete) , (Insert)

   • Trường hợp cơ sở (Nền móng của bảng DP):

     • dp[i][0] = i: Để biến một xâu có i ký tự thành xâu rỗng, cách duy nhất là thực hiện i phép xóa.
     • dp[0][j] = j: Để biến một xâu rỗng thành một xâu có j ký tự, cách duy nhất là thực hiện j phép chèn.

2.3. Code tham khảo

#include <bits/stdc++.h>
using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string strA, strB; cin >> strA >> strB; int lenA = strA.length(); int lenB = strB.length(); // dp[i][j] là chi phí tối thiểu để biến strA[0...i-1] thành strB[0...j-1] vector<vector<int>> dp(lenA + 1, vector<int>(lenB + 1)); // Trường hợp cơ sở for (int i = 0; i <= lenA; ++i) dp[i][0] = i; // Cần i phép xóa for (int j = 0; j <= lenB; ++j) dp[0][j] = j; // Cần j phép chèn // Tính toán dựa trên công thức truy hồi for (int i = 1; i <= lenA; ++i) { for (int j = 1; j <= lenB; ++j) { // Lưu ý chỉ số: dp[i][j] tương ứng với strA[i-1] và strB[j-1] if (strA[i - 1] == strB[j - 1]) { // Ký tự giống nhau, không tốn chi phí dp[i][j] = dp[i - 1][j - 1]; } else { // Ký tự khác nhau, tốn 1 chi phí + min của 3 lựa chọn int replaceCost = dp[i - 1][j - 1]; int deleteCost = dp[i - 1][j]; int insertCost = dp[i][j - 1]; dp[i][j] = 1 + min({replaceCost, deleteCost, insertCost}); } } } cout << dp[lenA][lenB]; return 0;
}

3. Tổng Kết

3.1. Tóm tắt các Pattern

3.2. Bài tập luyện tập

Lý thuyết chỉ là khởi đầu, luyện tập mới là chìa khóa. Anh em hãy thử sức với các bài tập sau để mài giũa kỹ năng nhé.

Luyện tập "Unbounded Choice Pattern":

• LeetCode 139. Word Break
• CSES - Minimizing Coins
• CSES - Coin Combinations I

Luyện tập "DP on Sequences Pattern":

• LeetCode 583. Delete Operation for Two Strings
• LeetCode 97. Interleaving String
• VNOI - QBSTR
• VNOI - PALIN (IOI 2000)

3.3. Lời kết

Chúng ta đã cùng nhau đi sâu vào tư duy đằng sau quy hoạch động, biến nó từ một công thức máy móc thành một bộ sưu tập các khuôn mẫu sống động. Giờ đây, anh em không chỉ có bản đồ, mà còn có cả la bàn và kỹ năng của một người đi săn thực thụ.

Chìa khóa để thực sự thành thạo DP không nằm ở việc học thuộc lòng lời giải, mà ở việc chủ động săn lùng, tìm kiếm những cấu trúc quen thuộc này trong mọi bài toán mới.

Hẹn gặp anh em trong bài viết về những patterns tiếp theo, see ya~