Bài 29.4. Các kỹ thuật tối ưu cơ bản trong DP
Bài 29.4. Các kỹ thuật tối ưu cơ bản trong DP
Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của chúng ta!
Trong các bài học trước, chúng ta đã cùng nhau tìm hiểu về sức mạnh của Quy hoạch động (DP) trong việc giải quyết một lớp lớn các bài toán bằng cách chia nhỏ chúng thành các bài toán con gối chồng. Tuy nhiên, sau khi đã xây dựng được công thức truy hồi (recurrence relation) cho một bài toán DP, đôi khi chúng ta nhận ra rằng giải pháp "thuần túy" ấy có thể yêu cầu một lượng bộ nhớ (không gian) hoặc thời gian rất lớn, vượt quá giới hạn cho phép của bài toán (ví dụ: giới hạn bộ nhớ 256MB, giới hạn thời gian 1-2 giây).
Đây chính là lúc chúng ta cần đến các kỹ thuật tối ưu hóa DP. Tối ưu DP không phải là việc "tìm ra công thức DP mới", mà là việc cải thiện công thức DP đã có để giảm thiểu tài nguyên sử dụng, đồng thời vẫn giữ nguyên tính đúng đắn của giải thuật. Trong bài viết này, chúng ta sẽ tập trung vào các kỹ thuật tối ưu cơ bản và thường gặp nhất.
Hãy cùng bắt đầu hành trình biến các giải pháp DP "ngốn tài nguyên" thành những giải pháp hiệu quả hơn!
1. Tối ưu hóa không gian (Space Optimization)
Một trong những lý do khiến DP sử dụng nhiều bộ nhớ là do chúng ta thường lưu trữ kết quả của tất cả các bài toán con trong một mảng (thường là 1D hoặc 2D). Tuy nhiên, khi tính toán trạng thái dp[i], ta có thật sự cần tất cả các trạng thái dp[j] với j < i không? Thường thì không! Đa số các bài toán DP có sự phụ thuộc lokal, nghĩa là dp[i] chỉ phụ thuộc vào một số lượng nhỏ các trạng thái ngay trước đó.
Nếu dp[i] chỉ phụ thuộc vào dp[i-1], dp[i-2], ..., dp[i-k] (với k nhỏ và cố định), thì chúng ta không cần lưu trữ toàn bộ mảng dp có kích thước N. Thay vào đó, ta chỉ cần lưu trữ k+1 giá trị gần nhất mà thôi.
Hãy xem xét một số ví dụ kinh điển.
Ví dụ 1.1: Dãy Fibonacci
Công thức truy hồi: F(n) = F(n-1) + F(n-2) với F(0)=0, F(1)=1.
Giải pháp DP "thuần túy" (lưu trữ O(N) không gian):
#include <iostream>
#include <vector>
int fib_naive_space(int n) {
if (n <= 1) {
return n;
}
std::vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2]; // dp[i] chỉ phụ thuộc dp[i-1] và dp[i-2]
}
return dp[n];
}
int main() {
int n = 10;
std::cout << "Fib(" << n << ") (Naive Space): " << fib_naive_space(n) << std::endl;
return 0;
}
Giải thích: Chúng ta dùng một vector dp có kích thước n+1 để lưu trữ tất cả các giá trị Fibonacci từ F(0) đến F(n). Khi tính dp[i], chúng ta truy cập dp[i-1] và dp[i-2]. Không gian sử dụng là O(N). Với N lớn, điều này có thể tốn bộ nhớ.
Giải pháp DP tối ưu không gian (O(1) không gian):
Nhận thấy rằng để tính F(n), chúng ta chỉ cần biết F(n-1) và F(n-2). Khi tiến lên tính F(n+1), ta sẽ cần F(n) (là kết quả vừa tính) và F(n-1) (là giá trị "trước đó" của F(n)). Như vậy, ta chỉ cần lưu trữ hai giá trị gần nhất mà thôi!
#include <iostream>
int fib_optimized_space(int n) {
if (n <= 1) {
return n;
}
int prev2 = 0; // Tương đương F(i-2)
int prev1 = 1; // Tương đương F(i-1)
int current; // Tương đương F(i)
for (int i = 2; i <= n; ++i) {
current = prev1 + prev2; // F(i) = F(i-1) + F(i-2)
// Cập nhật cho bước lặp tiếp theo:
// F(i-2) mới sẽ là F(i-1) cũ
prev2 = prev1;
// F(i-1) mới sẽ là F(i) vừa tính
prev1 = current;
}
return prev1; // prev1 lúc này đang giữ F(n)
}
int main() {
int n = 10;
std::cout << "Fib(" << n << ") (Optimized Space): " << fib_optimized_space(n) << std::endl;
return 0;
}
Giải thích: Chúng ta chỉ sử dụng ba biến (prev2, prev1, current) để lưu trữ các giá trị cần thiết. Khi tính current (tương ứng với F(i)), chúng ta cập nhật prev2 thành prev1 và prev1 thành current để chuẩn bị cho lần lặp kế tiếp (tính F(i+1)). Không gian sử dụng chỉ còn là O(1) - một hằng số, độc lập với N.
Ví dụ 1.2: Bài toán Cái túi 0/1 (0/1 Knapsack)
Bài toán: Cho N vật, mỗi vật có khối lượng w[i] và giá trị v[i]. Cần chọn một tập con các vật đặt vào cái túi có sức chứa W sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất.
Công thức DP "chuẩn" (sử dụng O(N*W) không gian): dp[i][w] là giá trị lớn nhất có thể đạt được khi xét i vật đầu tiên và sức chứa túi là w.
dp[i][w] = dp[i-1][w] (không chọn vật thứ i)
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i]) (nếu chọn vật thứ i và w >= w[i])
Chúng ta thường dùng mảng 2D dp[N+1][W+1]. Không gian là O(NW). Với N và W lớn (ví dụ N=1000, W=10000), O(1000 10000) = O(10^7) là chấp nhận được. Nhưng nếu W lớn hơn nhiều (ví dụ W=10^5 hoặc 10^6)? O(N*W) có thể vượt quá giới hạn bộ nhớ.
Giải pháp DP tối ưu không gian (O(W) không gian):
Quan sát công thức: dp[i][w] chỉ phụ thuộc vào các giá trị ở hàng i-1. Nghĩa là, khi tính toán cho vật thứ i, chúng ta chỉ cần kết quả của vật thứ i-1.
Ta có thể sử dụng mảng 1D dp[W+1]. dp[w] lúc này sẽ có ý nghĩa là giá trị lớn nhất đạt được với sức chứa w khi xét các vật từ đầu đến vật hiện tại đang xem xét.
Khi xử lý vật thứ i, ta sẽ cập nhật mảng 1D dp. Để tính dp[w] mới (xét vật i), ta cần dp[w] cũ (không xét vật i) và dp[w - w[i]] cũ (xét vật i, lấy giá trị của sức chứa còn lại khi xét vật i-1).
Điểm mấu chốt để tối ưu không gian 2D về 1D trong Knapsack là thứ tự lặp của biến trọng lượng w.
Nếu ta lặp w từ nhỏ đến lớn:
// Sai khi tối ưu không gian Knapsack 0/1
for (int i = 1; i <= N; ++i) { // Xét vật i
for (int w = w[i]; w <= W; ++w) { // Xét sức chứa w
// dp[w] cũ là giá trị tốt nhất với sức chứa w khi xét vật i-1
// dp[w - w[i]] cũ là giá trị tốt nhất với sức chứa w - w[i] khi xét vật i-1
// Muốn tính dp[w] mới (xét vật i):
// option1 = dp[w] (không chọn vật i, lấy kết quả của i-1)
// option2 = dp[w - w[i]] + v[i] (chọn vật i)
// dp[w] = max(option1, option2);
// Vấn đề: Khi tính dp[w], nếu w - w[i] < w, giá trị dp[w - w[i]] có thể đã bị cập nhật
// bằng kết quả của VẬT i (vì w - w[i] được tính trước w).
// Điều này làm sai bài toán 0/1 Knapsack (mỗi vật chỉ chọn 0 hoặc 1 lần).
// Nó biến thành bài toán Unbounded Knapsack (mỗi vật chọn nhiều lần).
dp[w] = std::max(dp[w], dp[w - w[i]] + v[i]); // SAI trong 0/1 Knapsack
}
}
Để đảm bảo khi tính dp[w] cho vật i, ta truy cập dp[w - w[i]] là giá trị trước khi xét vật i (nghĩa là giá trị khi chỉ xét vật i-1), ta phải lặp biến w từ lớn đến nhỏ:
#include <iostream>
#include <vector>
#include <algorithm>
int knapsack_optimized_space(int W, const std::vector<int>& weights, const std::vector<int>& values) {
int n = weights.size();
std::vector<int> dp(W + 1, 0); // dp[w]: max value for capacity w considering items processed so far
// Duyệt qua từng vật
for (int i = 0; i < n; ++i) {
int current_weight = weights[i];
int current_value = values[i];
// Duyệt qua sức chứa từ lớn đến nhỏ
// Nếu lặp từ nhỏ đến lớn, dp[w - current_weight] sẽ bị cập nhật
// bằng giá trị của vật i đó, làm sai logic 0/1 Knapsack.
for (int w = W; w >= current_weight; --w) {
// Lựa chọn 1: Không chọn vật i. Giá trị giữ nguyên là dp[w] cũ.
// Lựa chọn 2: Chọn vật i. Giá trị = giá trị tốt nhất với sức chứa còn lại (w - current_weight)
// khi CHƯA xét vật i (đảm bảo nhờ lặp w từ lớn đến nhỏ) + giá trị vật i.
dp[w] = std::max(dp[w], dp[w - current_weight] + current_value);
}
}
return dp[W];
}
int main() {
int W = 10;
std::vector<int> weights = {2, 3, 4, 5};
std::vector<int> values = {3, 4, 5, 6};
std::cout << "Max value for Knapsack (Optimized Space): " << knapsack_optimized_space(W, weights, values) << std::endl; // Expected: 9 (items with weights 4 and 5)
return 0;
}
Giải thích: Chúng ta chỉ sử dụng mảng 1D dp có kích thước W+1. Vòng lặp ngoài duyệt qua từng vật. Vòng lặp trong duyệt qua sức chứa từ W về current_weight. Khi tính dp[w] mới, dp[w] cũ đại diện cho việc không chọn vật hiện tại. dp[w - current_weight] + current_value đại diện cho việc chọn vật hiện tại; nhờ lặp từ lớn đến nhỏ, dp[w - current_weight] lúc này vẫn đang giữ giá trị tốt nhất khi chỉ xét các vật trước đó (vật i-1). Không gian sử dụng giảm từ O(N*W) xuống còn O(W), là một cải thiện đáng kể khi W lớn.
Tối ưu không gian là kỹ thuật cơ bản nhưng cực kỳ quan trọng, giúp chúng ta giải quyết các bài toán DP mà trước đó có thể bị giới hạn bởi bộ nhớ.
2. Tối ưu hóa thời gian chuyển trạng thái (Optimizing Transitions)
Thời gian tính toán cho một trạng thái dp[i] (hay dp[i][j]) từ các trạng thái phụ thuộc gọi là thời gian chuyển trạng thái. Đôi khi, công thức truy hồi yêu cầu tính tổng hoặc tìm min/max trên một khoảng các trạng thái trước đó. Nếu khoảng này có kích thước thay đổi hoặc lớn, thời gian chuyển trạng thái có thể là O(N) hoặc O(k) (với k là kích thước khoảng), dẫn đến tổng thời gian giải thuật là O(N^2) hoặc O(N*k).
Mục tiêu của tối ưu hóa thời gian chuyển trạng thái là giảm thời gian tính toán này, thường về O(1) hoặc O(log N), bằng cách sử dụng các cấu trúc dữ liệu hoặc kỹ thuật tính toán nhanh hơn. Một trong những kỹ thuật cơ bản và mạnh mẽ cho các bài toán có tính tổng trên khoảng là sử dụng Tổng tiền tố (Prefix Sum).
Ví dụ 2.1: Bài toán đếm số cách đi với bước nhảy giới hạn
Bài toán: Có N ô liên tiếp được đánh số từ 0 đến N-1. Bắt đầu từ ô 0, muốn đến ô N-1. Từ ô i, có thể nhảy đến ô j nếu i < j <= i + k (bước nhảy tối đa là k). Hỏi có bao nhiêu cách khác nhau để đi từ ô 0 đến ô N-1?
Công thức DP: Gọi dp[i] là số cách để đi từ ô 0 đến ô i.
dp[0] = 1 (có 1 cách để ở ô 0: không làm gì cả)
Đối với i > 0, để đến ô i, ta có thể nhảy từ bất kỳ ô j nào thỏa mãn i - k <= j < i.
dp[i] = sum(dp[j]) với j thuộc khoảng [max(0, i-k), i-1].
Giải pháp DP "thuần túy" (thời gian chuyển trạng thái O(k)):
#include <iostream>
#include <vector>
#include <numeric> // for std::accumulate (not used in final DP but good for understanding sum)
int count_ways_naive(int n, int k) {
if (n == 0) return 1;
std::vector<long long> dp(n, 0);
dp[0] = 1;
for (int i = 1; i < n; ++i) {
// Tính tổng dp[j] cho j từ max(0, i-k) đến i-1
for (int j = std::max(0, i - k); j < i; ++j) {
dp[i] += dp[j];
}
}
return dp[n - 1];
}
int main() {
int n = 6; // Đến ô 5
int k = 3; // Bước nhảy tối đa 3
// Path examples for n=6, k=3:
// 0->1->2->3->4->5
// 0->1->2->4->5
// 0->1->3->4->5
// 0->1->2->5
// 0->1->3->5
// 0->1->4->5
// 0->2->3->4->5
// 0->2->4->5
// 0->2->5
// 0->3->4->5
// 0->3->5
// ... and more
std::cout << "Number of ways (Naive): " << count_ways_naive(n, k) << std::endl; // Expected for n=6, k=3: 13 (from online sources)
return 0;
}
Giải thích: Vòng lặp ngoài duyệt qua các ô từ 1 đến n-1. Vòng lặp trong duyệt qua các ô j có thể nhảy đến ô i. Vòng lặp trong này chạy tối đa k lần. Tổng thời gian là O(N*k). Nếu k xấp xỉ N, thời gian sẽ là O(N^2).
Giải pháp DP tối ưu thời gian chuyển trạng thái (O(1) thời gian chuyển trạng thái) sử dụng Prefix Sum:
Để tính sum(dp[j]) cho j thuộc khoảng [a, b], chúng ta có thể sử dụng mảng tổng tiền tố. Gọi S[i] là tổng của dp[0] đến dp[i]. Khi đó, sum(dp[j] for j in [a, b]) = S[b] - S[a-1] (quy ước S[-1] = 0).
Trong bài toán này, dp[i] = sum(dp[j]) cho j từ max(0, i-k) đến i-1.
Sử dụng tổng tiền tố, dp[i] = S[i-1] - S[max(-1, i-k-1)]. (Lưu ý chỉ số: nếu khoảng bắt đầu từ 0, ta trừ đi S[-1] = 0).
Ta cần duy trì mảng DP và mảng tổng tiền tố.
#include <iostream>
#include <vector>
#include <numeric>
int count_ways_optimized(int n, int k) {
if (n == 0) return 1;
std::vector<long long> dp(n, 0);
std::vector<long long> prefix_sum(n, 0); // prefix_sum[i] = sum(dp[0]...dp[i])
dp[0] = 1;
prefix_sum[0] = 1;
for (int i = 1; i < n; ++i) {
// Tính dp[i] = sum(dp[j]) for j from max(0, i-k) to i-1
int start_idx = std::max(0, i - k);
int end_idx = i - 1;
long long sum_range;
if (start_idx == 0) {
// Nếu khoảng bắt đầu từ 0, tổng là prefix_sum[end_idx]
sum_range = prefix_sum[end_idx];
} else {
// Nếu khoảng bắt đầu từ start_idx > 0, tổng là prefix_sum[end_idx] - prefix_sum[start_idx - 1]
sum_range = prefix_sum[end_idx] - prefix_sum[start_idx - 1];
}
dp[i] = sum_range;
// Cập nhật mảng prefix_sum
prefix_sum[i] = prefix_sum[i - 1] + dp[i];
}
return dp[n - 1];
}
int main() {
int n = 6; // Đến ô 5
int k = 3; // Bước nhảy tối đa 3
std::cout << "Number of ways (Optimized): " << count_ways_optimized(n, k) << std::endl; // Expected: 13
return 0;
}
Giải thích: Chúng ta sử dụng thêm mảng prefix_sum. Khi tính dp[i], thay vì vòng lặp tính tổng O(k), ta sử dụng công thức O(1) dựa trên mảng prefix_sum. Sau khi tính được dp[i], ta cập nhật prefix_sum[i]. Tổng thời gian tính toán giảm từ O(N*k) xuống O(N) vì mỗi trạng thái dp[i] và prefix_sum[i] đều được tính trong O(1).
Kỹ thuật tổng tiền tố có thể áp dụng khi công thức chuyển trạng thái liên quan đến việc tính tổng (hoặc các phép toán kết hợp được như min/max trong một số trường hợp) trên một khoảng liên tục các trạng thái trước đó.
3. Những lưu ý khi tối ưu DP
- Luôn bắt đầu với giải pháp DP "chuẩn": Trước khi nghĩ đến tối ưu, hãy chắc chắn bạn đã có công thức truy hồi đúng và giải pháp DP (top-down memoization hoặc bottom-up tabulation) chính xác. Tối ưu một giải pháp sai sẽ không bao giờ cho kết quả đúng.
- Hiểu rõ sự phụ thuộc giữa các trạng thái: Đây là chìa khóa để tối ưu không gian. Trạng thái hiện tại phụ thuộc vào những trạng thái nào ở bước trước? Nếu chỉ phụ thuộc vào một số lượng nhỏ, cố định, bạn có thể tối ưu không gian.
- Phân tích thời gian chuyển trạng thái: Công thức tính trạng thái mới tốn bao nhiêu thời gian? Có phải là tính tổng/min/max trên một khoảng? Nếu có, các kỹ thuật như prefix sum, hoặc các cấu trúc dữ liệu nâng cao hơn (segment tree, Fenwick tree, deque cho Sliding Window Minimum/Maximum) có thể giúp giảm thời gian này. (Lưu ý: các cấu trúc dữ liệu nâng cao hơn thường không được coi là "kỹ thuật tối ưu cơ bản").
- Đánh đổi: Việc tối ưu không gian có thể làm cho code khó đọc và dễ sai hơn (như ví dụ Knapsack với vòng lặp ngược). Hãy cân nhắc đánh đổi giữa hiệu quả và độ phức tạp của code.
- Kiểm tra cận: Khi tối ưu không gian hoặc sử dụng prefix sum, hãy cẩn thận với các chỉ số mảng, đặc biệt là ở các trường hợp biên (ví dụ:
i-k < 0,start_idx - 1âm...).
Bài tập ví dụ:
Lũy thừa nhị phân.
Cho 2 số nguyên không âm a và b. Hãy tính a^b%(10^9+7). Kiến thức bạn cần sử dụng là Binary Exponentiation.
Input Format
2 số nguyên dương a, b.(1≤a,b≤10^9)
Constraints
.
Output Format
In ra kết quả của bài toán.
Ví dụ:
Dữ liệu vào
2 3Dữ liệu ra
8Chào bạn, đây là hướng dẫn giải bài Lũy thừa nhị phân sử dụng Binary Exponentiation trong C++:
- Hiểu bài toán: Cần tính
a^blấy dư cho10^9 + 7, vớiavàblà các số nguyên dương lớn. - Kỹ thuật sử dụng: Bài toán yêu cầu dùng Binary Exponentiation (hay còn gọi là Exponentiation by Squaring). Kỹ thuật này giúp tính lũy thừa nhanh hơn nhiều so với cách nhân lặp thông thường, đặc biệt hiệu quả với các số mũ lớn.
- Nguyên lý Binary Exponentiation: Dựa trên việc biểu diễn số mũ
bdưới dạng nhị phân. Ví dụa^10 = a^(1010_2) = a^(8+2) = a^8 * a^2. Ta có thể tínha^bbằng cách lặp qua các bit củab. Nếu bit thứicủablà 1, ta nhân kết quả tạm thời vớia^(2^i).a^(2^i)có thể tính được bằng cách bình phươnga^(2^(i-1)). - Thêm toán tử Modulo: Vì kết quả có thể rất lớn, ta cần thực hiện phép lấy dư
%(10^9 + 7)sau mỗi phép nhân để tránh tràn số. Quy tắc là(x * y) % M = ((x % M) * (y % M)) % M. - Cài đặt (ý tưởng):
- Sử dụng một hàm riêng (ví dụ:
power(a, b, mod)) để tínha^b % mod. - Trong hàm này, khởi tạo kết quả
res = 1. - Sử dụng một vòng lặp
while (b > 0). - Bên trong vòng lặp:
- Kiểm tra bit cuối cùng của
b(ví dụ:b % 2 == 1). Nếu là 1, nhân kết quả hiện tại (res) với cơ số hiện tại (a) và lấy modulo:res = (res * a) % mod. - Bình phương cơ số hiện tại (
a) và lấy modulo:a = (a * a) % mod. - Chia
bcho 2 (hoặc dịch phải 1 bit:b >>= 1).
- Kiểm tra bit cuối cùng của
- Sau vòng lặp,
reschứa kết quả cuối cùng. - Lưu ý quan trọng: Sử dụng kiểu dữ liệu
long longcho các biến lưu trữresvàabên trong hàmpowertrước khi thực hiện phép nhân và lấy modulo để tránh tràn số trong các phép nhân trung gian (ví dụ:res * ahoặca * a) khiavàrescòn lớn trước khi lấy modulo. - Định nghĩa hằng số
MOD = 1e9 + 7.
- Sử dụng một hàm riêng (ví dụ:
- Hàm
main: Đọcavàb, gọi hàmpowervớia, b, MODvà in kết quả.
Làm thêm nhiều bài tập miễn phí tại đây
Khóa học liên quan
Giảm giá!
Comments