Nhập Môn Quy Hoạch Động Cơ Bản

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

Hôm nay, tôi sẽ cùng anh em khám phá một trong những kỹ thuật mạnh mẽ và quan trọng bậc nhất trong kho vũ khí của một lập trình viên: Quy hoạch động (Dynamic Programming - DP).

Nhiều anh em khi mới nghe đến cái tên này thường cảm thấy e ngại, hình dung về những công thức toán học phức tạp và những dòng code khó hiểu vì độ khó của nó. Nhưng sự thật là, quy hoạch động không phải là một thuật toán cụ thể, mà là một phương pháp tư duy, một chiến lược giải quyết vấn đề. Một khi anh em nắm vững được cốt lõi của nó, anh em sẽ mở khóa được khả năng giải quyết một lớp các bài toán cực lớn mà trước đây có vẻ như bất khả thi.

Bài viết này được thiết kế dành riêng cho người mới bắt đầu. Chúng ta sẽ không đi thẳng vào những công thức khô khan. Thay vào đó, chúng ta sẽ bắt đầu bằng một câu chuyện, xây dựng một khung tư duy 3 bước đơn giản nhưng hiệu quả, và áp dụng nó để bẻ khóa những bài toán DP kinh điển nhất.

Hãy sẵn sàng, vì sau bài viết này, quy hoạch động sẽ không còn là nỗi sợ, mà sẽ trở thành vũ khí lợi hại của anh em.

1. Quy Hoạch Động Là Gì?

Hãy tưởng tượng anh em là một người thợ xây được giao nhiệm vụ xây một tòa tháp N tầng. Để tính tổng chi phí, một người thợ bình thường có thể sẽ tính chi phí cho tầng 1, rồi tính lại từ đầu cho tầng 1 và 2, rồi lại từ đầu cho tầng 1, 2, 3... Cách làm này cực kỳ tốn công và lặp lại.

Nhưng một người thợ xây thông minh sẽ làm khác. Anh ta biết rằng:

• Chi phí để xây xong 2 tầng chính là (chi phí xây xong 1 tầng) + (chi phí riêng của tầng 2).
• Chi phí để xây xong 3 tầng chính là (chi phí xây xong 2 tầng) + (chi phí riêng của tầng 3).
• ... Cứ như vậy, để tính chi phí xây tầng thứ i, anh ta chỉ cần lấy chi phí đã xây xong i-1 tầng (mà anh ta đã tính và ghi nhớ từ trước) rồi cộng thêm chi phí của tầng i.

Câu chuyện đơn giản này chứa đựng linh hồn của Quy hoạch động: chia một bài toán lớn thành các bài toán con nhỏ hơn, giải các bài toán con, lưu trữ kết quả của chúng và tái sử dụng khi cần thiết để giải quyết bài toán lớn hơn.

Sức mạnh thực sự của DP nằm ở khả năng tối ưu hóa độ phức tạp. Nó có thể biến những bài toán có lời giải ngây thơ (brute-force) với độ phức tạp lũy thừa (ví dụ $O(2^N)$), thành những lời giải có độ phức tạp đa thức (ví dụ $O(N^2)$ hoặc $O(N)$), chạy nhanh chóng với dữ liệu lớn. Đây chính là sự khác biệt giữa một bài toán được "Accepted" và một bài "Time Limit Exceeded".

2. Hai Trụ Cột Của Tư Duy Quy Hoạch Động

Để một bài toán có thể giải được bằng quy hoạch động, nó thường phải thỏa mãn hai tính chất quan trọng sau:

2.1. Bài toán con gối nhau (Overlapping Subproblems)

Đây là tình huống mà khi giải một bài toán bằng đệ quy, chúng ta phải giải đi giải lại cùng một bài toán con nhiều lần. Ví dụ kinh điển là tính số Fibonacci thứ n, với công thức $F(n) = F(n-1) + F(n-2)$. Khi tính $F(5)$, ta thấy $F(3)$ được tính 2 lần, $F(2)$ được tính 3 lần. Quy hoạch động giải quyết vấn đề này bằng cách đảm bảo mỗi bài toán con chỉ được tính một lần duy nhất, kết quả sẽ được lưu lại và sử dụng cho những lần sau.

2.2. Cấu trúc con tối ưu (Optimal Substructure)

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

Ví dụ: Đường đi ngắn nhất từ nhà (A) đến trường (C) qua tiệm sách (B) phải bao gồm đường đi ngắn nhất từ A đến B và đường đi ngắn nhất từ B đến C. Lời giải tối ưu của bài toán tổng thể (A đến C) phụ thuộc vào lời giải tối ưu của các bài toán con (A đến B và B đến C).

Tóm lại, triết lý của quy hoạch động là: Đừng bao giờ giải quyết cùng một vấn đề hai lần.

3. Công Thức 3 Bước Chinh Phục Mọi Bài Toán DP

Bây giờ, tôi sẽ hệ thống hóa tư duy quy hoạch động thành một quy trình 3 bước rõ ràng. Việc tuân thủ nghiêm ngặt trình tự này sẽ giúp anh em gỡ rối tư duy và tiếp cận bài toán một cách có hệ thống.

Bước 1: Định nghĩa Trạng thái DP

Đây là bước quan trọng nhất và cũng là bước khó nhất. Anh em cần tự hỏi: "Tôi cần lưu trữ thông tin gì về một bài toán con để có thể đưa ra quyết định cho các bước tiếp theo?"

Thông tin này được gọi là trạng thái, và thường được lưu trong mảng DP. dp[i] hoặc dp[i][j] đại diện cho lời giải tối ưu của một bài toán con cụ thể.

• Ví dụ: Gọi dp[i] có thể là "chi phí nhỏ nhất để đi đến hòn đá thứ i".
• Mẹo: Các tham số thay đổi trong lời giải đệ quy ngây thơ thường chính là các chiều của mảng DP. Nếu hàm đệ quy là solve(index), mảng DP có thể là dp[index]. Nếu hàm là solve(index, capacity), mảng DP có thể là dp[index][capacity].

Bước 2: Xác định Kết quả Bài toán

Sau khi đã định nghĩa được trạng thái, anh em cần xác định xem đáp án cuối cùng của bài toán nằm ở đâu trong mảng DP. Nó có thể là một phần tử cụ thể (ví dụ dp[N]) hoặc giá trị lớn nhất/nhỏ nhất trong toàn bộ mảng.

Bước 3: Xây dựng Công thức Truy hồi

Đây là lúc chúng ta kết nối các trạng thái lại với nhau. Anh em cần trả lời câu hỏi: "Làm thế nào để tính được dp[i] nếu tôi đã biết kết quả của các trạng thái trước đó (ví dụ dp[i-1], dp[i-2]...)?".

Công thức này gồm hai phần:

1. Bài toán cơ sở (Base Case): Những trạng thái nhỏ nhất, đơn giản nhất có thể giải ngay lập tức (ví dụ: dp[0] = 0).
2. Công thức chuyển trạng thái (Transition Formula): Biểu thức toán học mô tả cách dp[i] được tính toán từ các trạng thái đã giải trước đó.

Các hướng triển khai Quy hoạch động

• Top-Down (Đệ quy có nhớ - Memoization): Hướng tiếp cận này có luồng tư duy rất tự nhiên, giống hệt cách chúng ta suy nghĩ đệ quy thông thường:
  • Cách hoạt động: Anh em bắt đầu từ bài toán lớn nhất (ví dụ solve(N)), sau đó chia nó thành các bài toán con nhỏ hơn (solve(N-1), solve(N-2)...).
  • Mấu chốt: Mỗi khi tính xong kết quả của một bài toán con, anh em lưu nó vào một bảng ghi nhớ (thường là mảng hoặc map). Ở những lần gọi đệ quy sau, nếu gặp lại đúng bài toán con đó, anh em chỉ cần lấy kết quả đã lưu ra dùng lại thay vì phải tính toán lại từ đầu.
• Bottom-Up (Bảng phương án - Tabulation): Hướng tiếp cận này có tư duy ngược lại, mang tính hệ thống hơn:
  • Cách hoạt động: Anh em bắt đầu từ những "viên gạch nền móng", tức là giải quyết các bài toán con nhỏ nhất (base case) trước.
  • Mấu chốt: Anh em sẽ dùng vòng lặp để điền vào một cái bảng (mảng DP), tính toán các trạng thái theo một thứ tự hợp lý (ví dụ từ i = 1 đến N). Kết quả của bài toán con sau được xây dựng dựa trên kết quả của các bài toán con trước đó đã được tính và lưu trong bảng.

4. Thực Chiến

Lý thuyết sẽ trở nên vô nghĩa nếu không được thực hành. Bây giờ, chúng ta sẽ áp dụng khung tư duy 3 bước vào ba bài toán quy hoạch động kinh điển.

4.1. Ví dụ 1: Chú Ếch Nhảy (Frog 1)

Đây là bài toán "Hello World" của quy hoạch động.

• Bài toán: Có N hòn đá. Một chú ếch ở hòn đá 1, có thể nhảy đến hòn đá i+1 hoặc i+2. Chi phí nhảy từ đá i đến j là $|h_i - h_j|$ trong đó $h_i$ và $h_j$ lầ lượt là độ cao của đá i và đá j. Tìm tổng chi phí nhỏ nhất để đến hòn đá N.

• Phân tích 3 bước:

  1. Trạng thái: Gọi dp[i] là tổng chi phí nhỏ nhất để đến được hòn đá thứ i.
  2. Kết quả: dp[N].
  3. Công thức truy hồi:
     • Để đến đá i, ếch phải nhảy từ i-1 hoặc i-2.
     • Công thức chuyển trạng thái: dp[i] = min(dp[i-1] + |h[i] - h[i-1]|, dp[i-2] + |h[i] - h[i-2]|).
     • Base Case: dp[1] = 0. dp[2] = |h[2] - h[1]|.

• Triển khai Top-Down (Đệ quy có nhớ):

#include <bits/stdc++.h>
using namespace std; const int INF = 1e9;
vector<int> heights;
vector<int> memo;
int numStones; int solve(int stoneIndex)
{ // Base case: đã ở hòn đá 1 if (stoneIndex == 1) return 0; // Nếu kết quả đã được tính, trả về ngay if (memo[stoneIndex] != -1) return memo[stoneIndex]; // Tính toán đệ quy int result = INF; // Lựa chọn 1: Nhảy từ stoneIndex - 1 result = min(result, solve(stoneIndex - 1) + abs(heights[stoneIndex] - heights[stoneIndex - 1])); // Lựa chọn 2: Nhảy từ stoneIndex - 2 (chỉ khả thi khi stoneIndex > 2) if (stoneIndex > 2) result = min(result, solve(stoneIndex - 2) + abs(heights[stoneIndex] - heights[stoneIndex - 2])); // Lưu kết quả vào bảng ghi nhớ và trả về return memo[stoneIndex] = result;
} int main()
{ cin >> numStones; heights.resize(numStones + 1); memo.assign(numStones + 1, -1); // Khởi tạo mảng ghi nhớ với giá trị -1 for (int i = 1; i <= numStones; ++i) cin >> heights[i]; cout << solve(numStones); return 0;
}

• Triển khai Bottom-Up:

#include <bits/stdc++.h>
using namespace std; int main()
{ int numStones; cin >> numStones; vector<int> heights(numStones + 1); for (int i = 1; i <= numStones; ++i) cin >> heights[i]; if (numStones == 1) { cout << 0; return 0; } vector<int> dp(numStones + 1); // Base cases dp[1] = 0; dp[2] = abs(heights[2] - heights[1]); // Điền bảng dp từ dưới lên for (int i = 3; i <= numStones; ++i) { int cost1 = dp[i - 1] + abs(heights[i] - heights[i - 1]); int cost2 = dp[i - 2] + abs(heights[i] - heights[i - 2]); dp[i] = min(cost1, cost2); } cout << dp[numStones]; return 0;
}

4.2. Ví dụ 2: Siêu Trộm và Cái Túi (0/1 Knapsack)

Bài toán này giới thiệu DP 2 chiều và khái niệm lựa chọn.

• Bài toán: Một tên trộm có túi sức chứa $W$. Có $N$ món đồ, mỗi món có trọng lượng $w_i$ và giá trị $v_i$. Tên trộm nên chọn đồ nào để tổng giá trị lớn nhất mà không vượt quá sức chứa túi?

• Phân tích 3 bước:

  1. Trạng thái: Gọi dp[i][j] là tổng giá trị lớn nhất có thể đạt được khi xét i món đồ đầu tiên với túi có sức chứa j.
  2. Kết quả: dp[N][W].
  3. Công thức truy hồi: Khi xét món đồ i với sức chứa j:
     • Lựa chọn 1 (Không lấy món i): Giá trị là dp[i-1][j].
     • Lựa chọn 2 (Lấy món i, nếu j >= w[i]): Giá trị là v[i] + dp[i-1][j - w[i]].
     • Công thức chuyển trạng thái: dp[i][j] = max(Lựa chọn 1, Lựa chọn 2).
     • Base Case: dp[0][j] = 0 và dp[i][0] = 0.

• Triển khai Top-Down (Đệ quy có nhớ):

#include <bits/stdc++.h>
using namespace std; int numItems, maxWeight;
vector<int> weights, values;
vector<vector<int>> memo; // itemIndex là chỉ số của món đồ đang xét (0-based)
int solve(int itemIndex, int currentWeight)
{ // Base case: đã xét hết đồ hoặc túi hết sức chứa if (itemIndex < 0 || currentWeight == 0) return 0; // Nếu đã tính, trả về kết quả if (memo[itemIndex][currentWeight] != -1) return memo[itemIndex][currentWeight]; // Lựa chọn 1: Không lấy món đồ thứ itemIndex int result = solve(itemIndex - 1, currentWeight); // Lựa chọn 2: Lấy món đồ thứ itemIndex (nếu có thể) if (weights[itemIndex] <= currentWeight) result = max(result, values[itemIndex] + solve(itemIndex - 1, currentWeight - weights[itemIndex])); // Ghi nhớ và trả về return memo[itemIndex][currentWeight] = result;
} int main()
{ cin >> numItems >> maxWeight; weights.resize(numItems); values.resize(numItems); memo.assign(numItems, vector<int>(maxWeight + 1, -1)); for (int i = 0; i < numItems; ++i) cin >> weights[i] >> values[i]; // Gọi đệ quy từ món đồ cuối cùng (chỉ số numItems - 1) cout << solve(numItems - 1, maxWeight); return 0;
}

• Triển khai (Bottom-Up):

#include <bits/stdc++.h>
using namespace std; int main()
{ int numItems, maxWeight; cin >> numItems >> maxWeight; vector<int> weights(numItems + 1), values(numItems + 1); for (int i = 1; i <= numItems; ++i) cin >> weights[i] >> values[i]; vector<vector<long long>> dp(numItems + 1, vector<long long>(maxWeight + 1, 0)); for (int i = 1; i <= numItems; ++i) { for (int j = 1; j <= maxWeight; ++j) { // Lựa chọn 1: không lấy món i dp[i][j] = dp[i - 1][j]; // Lựa chọn 2: lấy món i (nếu có thể) if (j >= weights[i]) dp[i][j] = max(dp[i][j], values[i] + dp[i - 1][j - weights[i]]); } } cout << dp[numItems][maxWeight]; return 0;
}

4.3. Ví dụ 3: Dãy Con Tăng Dài Nhất (LIS)

Một ví dụ 1D nhưng đòi hỏi sự tinh tế trong việc định nghĩa trạng thái.

• Bài toán: Cho một dãy N số nguyên. Tìm độ dài của dãy con tăng dài nhất.

• Phân tích 3 bước:

  1. Trạng thái: Gọi dp[i] là độ dài của dãy con tăng dài nhất mà kết thúc tại phần tử A[i].
  2. Kết quả: Vì dãy con tăng dài nhất có thể kết thúc ở bất kỳ đâu, kết quả là max(dp[1], ..., dp[N]).
  3. Công thức truy hồi:
     • Để tính dp[i], ta tìm một phần tử A[j] đứng trước nó (j < i) sao cho A[j] < A[i] và dp[j] là lớn nhất. Hay nói cách khác là chúng ta sẽ tìm một dãy con kết thúc tại phần tử A[j] trước đó (j < i) sao cho độ dài của dãy con đó là lớn nhất (dp[j]) sau đó ta sẽ thêm phần tử A[i] vào cuối dãy con đó và ta sẽ có được dãy con tăng dài nhất kết thúc tại phần tử A[i].
     • Công thức chuyển trạng thái: dp[i] = 1 + max({dp[j]}) với mọi j < i và A[j] < A[i].
     • Base Case: dp[i] = 1 cho mọi i (dãy con chỉ chứa chính nó).

• Triển khai Top-Down (Đệ quy có nhớ):

#include <bits/stdc++.h>
using namespace std; vector<int> sequence;
vector<int> memo;
int sequenceLength; // Hàm này tính độ dài LIS kết thúc tại chỉ số currentIndex
int solve(int currentIndex)
{ // Nếu đã tính, trả về kết quả if (memo[currentIndex] != -1) return memo[currentIndex]; // Base case: LIS kết thúc tại currentIndex có ít nhất 1 phần tử (chính nó) int maxLength = 1; // Duyệt qua tất cả các phần tử trước currentIndex for (int prevIndex = 0; prevIndex < currentIndex; ++prevIndex) if (sequence[prevIndex] < sequence[currentIndex]) maxLength = max(maxLength, 1 + solve(prevIndex)); return memo[currentIndex] = maxLength;
} int main()
{ cin >> sequenceLength; if (sequenceLength == 0) { cout << 0; return 0; } sequence.resize(sequenceLength); memo.assign(sequenceLength, -1); for (int i = 0; i < sequenceLength; ++i) cin >> sequence[i]; int finalResult = 0; // Gọi hàm solve cho mọi vị trí kết thúc có thể for (int i = 0; i < sequenceLength; ++i) finalResult = max(finalResult, solve(i)); cout << finalResult; return 0;
}

• Triển khai (Bottom-Up):

#include <bits/stdc++.h>
using namespace std; int main()
{ int sequenceLength; cin >> sequenceLength; if (sequenceLength == 0) { cout << 0; return 0; } vector<int> sequence(sequenceLength); for (int i = 0; i < sequenceLength; ++i) cin >> sequence[i]; vector<int> dp(sequenceLength, 1); for (int i = 1; i < sequenceLength; ++i) for (int j = 0; j < i; ++j) if (sequence[j] < sequence[i]) dp[i] = max(dp[i], dp[j] + 1); int result = 0; for (int len : dp) result = max(result, len); // Hoặc đơn giản hơn: cout << *max_element(dp.begin(), dp.end()) << endl; cout << result; return 0;
}

5. Top-Down vs. Bottom-Up: Chọn Hướng Nào?

Cả hai phong cách đều có ưu và nhược điểm. Việc chọn cái nào phụ thuộc vào bài toán và sở thích của anh em.

Lời khuyên của tôi:

• Khi mới làm quen: Hãy bắt đầu với Top-Down. Nó gần với cách suy nghĩ tự nhiên hơn.
• Khi thi đấu: Chọn phương pháp mà anh em tự tin và code nhanh nhất.
• Khi cần tối ưu: Bottom-Up là lựa chọn vượt trội để tối ưu không gian lưu trữ.
• Chiến lược hiệu quả: Dùng tư duy Top-Down để tìm công thức, sau đó triển khai bằng Bottom-Up để có hiệu suất tốt nhất.

6. Tổng Kết

Quy hoạch động không phải là một ngọn núi thẳng đứng, mà là một dãy các ngọn đồi. Mỗi bài toán anh em giải được là một ngọn đồi đã vượt qua. Hãy kiên trì leo từng ngọn đồi, bắt đầu từ những bài cơ bản nhất. Dần dần anh em sẽ hình thành được tư duy và kinh nghiệm giải bài.

Ghi nhớ "Bí kíp":

• Tư tưởng: Chia để trị và ghi nhớ.
• Hai trụ cột: Bài toán con gối nhau và Cấu trúc con tối ưu.
• Khung 3 bước: Định nghĩa trạng thái $\rightarrow$ Xác định kết quả $\rightarrow$ Tìm công thức truy hồi.
• Đừng vội code: Dành thời gian phân tích trên giấy trước.
• Đừng học thuộc lòng: Hãy hiểu cách tư duy và nhận ra các mẫu quen thuộc.

Bài tập luyện tập:

1. Nền tảng (DP 1 chiều):
   • AtCoder DP Contest: A - Frog 1, B - Frog 2, C - Vacation
   • LeetCode: Climbing Stairs, House Robber
2. DP 2 chiều & Bài toán lựa chọn:
   • AtCoder DP Contest: D - Knapsack 1, E - Knapsack 2
   • LeetCode: Unique Paths, Minimum Path Sum
3. DP trên chuỗi & Dãy số:
   • AtCoder DP Contest: F - LCS
   • LeetCode: Longest Common Subsequence, Longest Increasing Subsequence, Edit Distance
4. Thử thách thêm:
   • LeetCode: Coin Change, Coin Change II

Hy vọng sau bài viết này anh em sẽ hiểu rõ hơn về kỹ thuật Quy hoạch động. Đừng quên luyện tập thường xuyên để nâng cao kỹ năng của bản thân nhé, see ya~