Bài 26.4. Tối ưu không gian trong QHĐ
Bài 26.4. Tối ưu không gian trong QHĐ
Quy hoạch động (QHĐ) là một công cụ cực kỳ mạnh mẽ để giải quyết nhiều bài toán phức tạp, từ các bài toán tối ưu trên dãy, trên lưới, đến các bài toán trên cây hay đồ thị. Bản chất của QHĐ là lưu trữ kết quả của các bài toán con để tránh tính toán lặp lại. Điều này thường dẫn đến việc sử dụng một bảng DP (thường là mảng 1 chiều hoặc 2 chiều, hoặc cấu trúc dữ liệu phức tạp hơn) để lưu trữ các trạng thái.
Tuy nhiên, không gian lưu trữ của bảng DP có thể trở thành một nút thắt cổ chai nghiêm trọng. Với các bài toán có không gian trạng thái lớn, chẳng hạn như bài toán Cái túi 0/1 với trọng lượng tối đa rất lớn, hoặc các bài toán trên chuỗi dài, bảng DP truyền thống có thể yêu cầu lượng bộ nhớ vượt quá giới hạn cho phép, dẫn đến lỗi Memory Limit Exceeded (MLE).
May mắn thay, trong nhiều trường hợp, chúng ta không cần lưu trữ toàn bộ bảng DP. Khi tính toán một trạng thái dp[i], chúng ta thường chỉ cần một số lượng hữu hạn các trạng thái trước đó (ví dụ: dp[i-1], dp[i-2] trong bài Fibonacci, hoặc dp[i-1][j] và dp[i][j-1] trong bài LCS). Nếu sự phụ thuộc này chỉ giới hạn trong một "phạm vi" nhỏ xung quanh trạng thái hiện tại, chúng ta hoàn toàn có thể tối ưu không gian bộ nhớ, giảm kích thước bảng DP từ O(N) hoặc O(N*M) xuống O(K), trong đó K là một hằng số nhỏ hoặc một chiều kích thước khác của bài toán.
Kỹ thuật tối ưu không gian dựa trên việc nhận ra rằng khi chúng ta tiến từ trạng thái i sang i+1, các giá trị dp của trạng thái i-k (với k đủ lớn) có thể không còn cần thiết nữa để tính toán các trạng thái trong tương lai. Chúng ta chỉ cần giữ lại những thông tin quan trọng từ các bước trước để phục vụ cho bước hiện tại.
Hãy cùng khám phá kỹ thuật này qua một số ví dụ kinh điển trong QHĐ, đi từ đơn giản đến phức tạp hơn.
Ví dụ 1: Dãy Fibonacci
Bài toán: Tính số Fibonacci thứ n, ký hiệu là F(n). Công thức: F(n) = F(n-1) + F(n-2) với F(0) = 0, F(1) = 1.
QHĐ thông thường (Không gian O(n))
Chúng ta có thể dùng một mảng dp kích thước n+1 để lưu trữ các giá trị từ F(0) đến F(n).
#include <vector>
long long fibonacci_on(int n) {
if (n <= 1) return n; // F(0) = 0, F(1) = 1
std::vector<long long> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
// Tính F(i) dựa trên F(i-1) và F(i-2) đã được lưu
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Giải thích: Mảng dp có kích thước n+1 lưu trữ toàn bộ lịch sử tính toán. Khi tính dp[i], chúng ta truy cập các phần tử dp[i-1] và dp[i-2]. Không gian sử dụng là O(n).
Tối ưu không gian (Không gian O(1))
Quan sát công thức F(n) = F(n-1) + F(n-2), để tính F(n), chúng ta chỉ cần hai giá trị ngay trước nó: F(n-1) và F(n-2). Khi chuyển sang tính F(n+1), chúng ta sẽ cần F(n) và F(n-1). Giá trị F(n-2) không còn cần thiết nữa. Điều này gợi ý rằng chúng ta chỉ cần lưu trữ hai giá trị gần nhất thay vì toàn bộ mảng.
Chúng ta có thể dùng ba biến: một biến lưu F(i-2), một biến lưu F(i-1), và một biến để tính F(i). Sau khi tính xong F(i), chúng ta cập nhật hai biến lưu trữ để chuẩn bị cho bước tiếp theo (tính F(i+1)).
long long fibonacci_o1(int n) {
if (n <= 1) return n; // F(0) = 0, F(1) = 1
long long prev2 = 0; // Ban đầu tương ứng F(0)
long long prev1 = 1; // Ban đầu tương ứng F(1)
long long current; // Biến tạm để tính F(i)
// Bắt đầu từ i = 2 để tính F(2), ..., F(n)
for (int i = 2; i <= n; ++i) {
// F(i) = F(i-1) + F(i-2)
current = prev1 + prev2;
// Chuẩn bị cho lần lặp tiếp theo (tính F(i+1))
// F(i-1) hiện tại (lưu ở prev1) sẽ trở thành F((i+1)-2) = F(i-1) mới
prev2 = prev1;
// F(i) vừa tính (lưu ở current) sẽ trở thành F((i+1)-1) = F(i) mới
prev1 = current;
}
// Sau khi vòng lặp kết thúc, prev1 đang lưu giá trị F(n) cuối cùng
return prev1;
}
Giải thích: Chúng ta chỉ sử dụng ba biến kiểu long long (prev2, prev1, current) để lưu trữ các giá trị cần thiết. Kích thước bộ nhớ là hằng số O(1), không phụ thuộc vào n. Độ phức tạp thời gian vẫn là O(n) vì chúng ta vẫn cần thực hiện n bước tính toán. Đây là một ví dụ điển hình của việc tối ưu không gian mà không ảnh hưởng đến thời gian.
Ví dụ 2: Leo cầu thang
Bài toán: Có n bậc thang. Mỗi lần bạn có thể bước 1 hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để leo đến đỉnh (bậc thứ n).
Đây là một bài toán có cấu trúc tương tự Fibonacci. Gọi dp[i] là số cách để leo đến bậc thứ i. Để đến được bậc i, bạn có thể từ bậc i-1 (bước 1 bậc) hoặc từ bậc i-2 (bước 2 bậc). Do đó, số cách đến bậc i là tổng số cách đến bậc i-1 và bậc i-2.
Công thức truy hồi: dp[i] = dp[i-1] + dp[i-2]
Điều kiện cơ sở:
dp[0] = 1: Có 1 cách để ở bậc 0 (không làm gì).dp[1] = 1: Có 1 cách để đến bậc 1 (bước 1 bậc từ bậc 0). (Lưu ý: một số định nghĩa có thể dùngdp[1]=1, dp[2]=2, dẫn đến điều kiện cơ sở khác một chút, nhưng cấu trúc truy hồi vẫn giữ nguyên).
QHĐ thông thường (Không gian O(n))
#include <vector> // Cần thiết cho std::vector
int climbStairs_on(int n) {
if (n == 0) return 1;
if (n == 1) return 1; // Base cases
std::vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Giải thích: Tương tự Fibonacci, sử dụng mảng DP kích thước O(n) để lưu trữ số cách đến từng bậc.
Tối ưu không gian (Không gian O(1))
Vì công thức truy hồi hoàn toàn giống Fibonacci (dp[i] chỉ phụ thuộc vào dp[i-1] và dp[i-2]), kỹ thuật tối ưu không gian cũng tương tự. Chúng ta chỉ cần lưu trữ hai giá trị trước đó.
int climbStairs_o1(int n) {
if (n == 0) return 1;
if (n == 1) return 1; // Base cases
int prev2 = 1; // Tương ứng dp[0]
int prev1 = 1; // Tương ứng dp[1]
int current;
for (int i = 2; i <= n; ++i) {
// dp[i] = dp[i-1] + dp[i-2]
current = prev1 + prev2;
// Cập nhật trạng thái cho lần lặp tiếp theo
prev2 = prev1;
prev1 = current;
}
// Sau vòng lặp, prev1 lưu giá trị dp[n]
return prev1;
}
Giải thích: Chỉ sử dụng ba biến cố định để theo dõi hai giá trị trước đó cần thiết. Không gian sử dụng là O(1).
Ví dụ 3: Bài toán tổng con (Subset Sum)
Bài toán: Cho một tập hợp các số nguyên dương nums và một tổng mục tiêu target. Xác định xem có tồn tại một tập con của nums mà tổng các phần tử của nó bằng target hay không.
QHĐ thông thường (Không gian O(n * target))
Gọi n là số lượng phần tử trong nums.
Gọi dp[i][j] là một giá trị boolean, cho biết liệu có thể tạo ra tổng j chỉ sử dụng các phần tử từ 0 đến i-1 trong mảng nums.
Kích thước bảng DP sẽ là (n+1) x (target+1).
Công thức truy hồi để tính dp[i][j] (sử dụng nums[i-1]):
- Không sử dụng
nums[i-1]: Khả năng tạo ra tổngjphụ thuộc vào việc có thể tạo ra tổngjchỉ với các phần tử từ0đếni-2. Tức làdp[i-1][j]. - Sử dụng
nums[i-1]: Chỉ có thể xảy ra nếuj >= nums[i-1]. Nếu có thể, khả năng tạo ra tổngjphụ thuộc vào việc có thể tạo ra tổngj - nums[i-1]chỉ với các phần tử từ0đếni-2. Tức làdp[i-1][j - nums[i-1]].
Vậy, dp[i][j] = dp[i-1][j] || (j >= nums[i-1] && dp[i-1][j - nums[i-1]]).
Điều kiện cơ sở:
dp[0][0] = true: Có thể tạo tổng 0 với tập rỗng.dp[i][0] = truecho mọii: Tổng 0 luôn có thể tạo ra.dp[0][j] = falsecho mọij > 0: Không thể tạo tổng dương nào với tập rỗng.
#include <vector> // Cần thiết cho std::vector
#include <numeric> // Có thể cần cho các hàm tiện ích, không bắt buộc cho core logic
bool subsetSum_on_target(const std::vector<int>& nums, int target) {
int n = nums.size();
// dp[i][j]: có thể tạo tổng j từ 0..i-1 phần tử đầu tiên không?
// Kích thước (n+1) x (target+1)
std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(target + 1, false));
// Điều kiện cơ sở: tổng 0 luôn có thể tạo ra
for (int i = 0; i <= n; ++i) {
dp[i][0] = true;
}
// Duyệt qua từng phần tử nums[i-1] (từ i=1 đến n)
for (int i = 1; i <= n; ++i) {
int num = nums[i - 1]; // Phần tử hiện tại đang xem xét
// Duyệt qua các tổng j (từ 1 đến target)
for (int j = 1; j <= target; ++j) {
// Case 1: Không sử dụng num
dp[i][j] = dp[i - 1][j];
// Case 2: Sử dụng num, nếu j đủ lớn
if (j >= num) {
// Có thể tạo tổng j nếu không dùng num HOẶC có thể tạo tổng j-num và dùng num
dp[i][j] = dp[i][j] || dp[i - 1][j - num];
}
}
}
return dp[n][target]; // Kết quả cuối cùng nằm ở dp[n][target]
}
Giải thích: Bảng dp 2 chiều kích thước (n+1) x (target+1) lưu trữ tất cả các trạng thái trung gian. Việc tính dp[i][j] chỉ dựa vào các giá trị ở hàng i-1. Không gian lưu trữ là O(n * target). Nếu target rất lớn, điều này có thể gây MLE.
Tối ưu không gian (Không gian O(target))
Vì để tính hàng i, chúng ta chỉ cần thông tin từ hàng i-1, chúng ta có thể giảm bảng DP từ 2 chiều xuống 1 chiều. Chúng ta sẽ sử dụng một mảng 1 chiều dp kích thước target + 1. Mảng này sẽ tái sử dụng không gian: ở đầu vòng lặp xử lý phần tử nums[i-1], dp[j] sẽ lưu trữ dp[i-1][j]. Sau khi xử lý xong phần tử đó, dp[j] sẽ được cập nhật để lưu trữ dp[i][j].
Khi tính toán dp[j] mới (tương ứng dp[i][j]), chúng ta cần dp[i-1][j] và dp[i-1][j - nums[i-1]].
Nếu chúng ta lặp qua j từ 1 đến target:
Để tính dp[i][j], ta cần dp[i-1][j] (là dp[j] hiện tại) và dp[i-1][j - nums[i-1]].
dp[j] = dp[j] || (j >= num && dp[j - num])
Vấn đề: Khi chúng ta đến j, giá trị dp[j - num] trong mảng 1 chiều có thể đã bị cập nhật dựa trên num hiện tại (nó đã trở thành dp[i][j-num]), thay vì giá trị cũ (dp[i-1][j-num]) mà chúng ta thực sự cần!
Để giải quyết vấn đề này, chúng ta cần đảm bảo rằng khi tính dp[j], giá trị dp[j - num] mà chúng ta truy cập vẫn là giá trị từ trạng thái trước đó (tức là từ hàng i-1). Điều này có thể đạt được bằng cách lặp qua j từ target xuống đến num.
Khi lặp j từ target xuống num:
dp[j] mới (tương ứng dp[i][j]) sẽ phụ thuộc vào:
dp[j]cũ (tương ứngdp[i-1][j]) - đây là giá trị hiện tại ởdp[j]trước khi nó bị ghi đè.dp[j - num]cũ (tương ứngdp[i-1][j - num]) - vì chúng ta lặp ngược,dp[j - num]vẫn chưa bị cập nhật trong lần lặp hiện tại khi chúng ta tínhdp[j](doj - num < j, nó sẽ được xử lý sau).
Công thức cập nhật khi lặp ngược j từ target xuống num:
dp[j] = dp[j] || dp[j - num] (áp dụng nếu j >= num)
#include <vector> // Cần thiết cho std::vector
bool subsetSum_o_target(const std::vector<int>& nums, int target) {
// dp[j]: có thể tạo tổng j sử dụng các số đã xem xét cho đến hiện tại không?
// Kích thước (target+1)
std::vector<bool> dp(target + 1, false);
// Điều kiện cơ sở: tổng 0 luôn có thể tạo ra
dp[0] = true;
// Duyệt qua từng số trong mảng nums
for (int num : nums) {
// Duyệt qua các tổng có thể đạt được TỪ LỚN ĐẾN BÉ
// Chỉ cần duyệt từ target xuống num, vì tổng < num không thể sử dụng num
for (int j = target; j >= num; --j) {
// Có thể tạo tổng j nếu:
// 1. Đã có thể tạo tổng j mà không dùng num (dp[j] hiện tại - tương ứng dp[i-1][j])
// HOẶC
// 2. Có thể tạo tổng j - num và dùng num (dp[j - num] hiện tại - tương ứng dp[i-1][j-num] do lặp ngược)
dp[j] = dp[j] || dp[j - num];
}
// Sau khi vòng lặp j kết thúc, mảng dp hiện tại đã được cập nhật
// để phản ánh khả năng tạo tổng với num hiện tại ĐƯỢC thêm vào tập các số đã xét.
}
return dp[target]; // Kết quả cuối cùng là dp[target] sau khi duyệt hết các số
}
Giải thích: Chúng ta sử dụng một mảng 1 chiều dp kích thước target + 1. Vòng lặp ngoài duyệt qua từng số num trong mảng đầu vào nums. Vòng lặp trong duyệt qua các tổng j từ target xuống đến num. Lặp ngược j là chìa khóa để đảm bảo rằng khi tính dp[j], giá trị dp[j - num] mà chúng ta truy cập vẫn là giá trị từ trạng thái trước khi xem xét num hiện tại, tương ứng với dp[i-1][j-num] trong bảng 2D gốc. Kỹ thuật này giảm không gian lưu trữ xuống O(target).
Ví dụ 4: Độ dài dãy con chung dài nhất (LCS)
Bài toán: Cho hai chuỗi text1 và text2. Tìm độ dài của dãy con chung dài nhất của chúng.
QHĐ thông thường (Không gian O(m * n))
Gọi m là độ dài của text1 và n là độ dài của text2.
Gọi dp[i][j] là độ dài dãy con chung dài nhất của text1[0...i-1] và text2[0...j-1].
Kích thước bảng DP sẽ là (m+1) x (n+1).
Công thức truy hồi:
- Nếu
text1[i-1] == text2[j-1]:dp[i][j] = dp[i-1][j-1] + 1. (Ký tự cuối cùng khớp, thêm 1 vào LCS của phần chuỗi còn lại). - Nếu
text1[i-1] != text2[j-1]:dp[i][j] = max(dp[i-1][j], dp[i][j-1]). (Ký tự cuối không khớp, lấy kết quả tốt nhất từ việc bỏ qua ký tự cuối củatext1hoặctext2).
Điều kiện cơ sở:
dp[i][0] = 0cho mọii(LCS với chuỗi rỗng là 0).dp[0][j] = 0cho mọij(LCS với chuỗi rỗng là 0).
#include <vector> // Cần thiết cho std::vector
#include <string> // Cần thiết cho std::string
#include <algorithm> // Cần thiết cho std::max
int longestCommonSubsequence_omn(const std::string& text1, const std::string& text2) {
int m = text1.length();
int n = text2.length();
// dp[i][j]: LCS of text1[0...i-1] and text2[0...j-1]
// Kích thước (m+1) x (n+1)
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Điều kiện cơ sở đã được khởi tạo sẵn (tất cả = 0)
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]; // Kết quả cuối cùng
}
Giải thích: Bảng dp 2 chiều kích thước (m+1) x (n+1). Để tính dp[i][j], chúng ta cần các giá trị dp[i-1][j-1], dp[i-1][j], và dp[i][j-1]. Không gian lưu trữ là O(m * n).
Tối ưu không gian (Không gian O(min(m, n)))
Quan sát công thức truy hồi, để tính dp[i][j], chúng ta cần các giá trị ở hàng trước đó (i-1) và giá trị ở cột trước đó trên hàng hiện tại (i, j-1). Điều này cho phép chúng ta tối ưu không gian bằng cách chỉ lưu trữ một số lượng hàng cố định.
Nếu chúng ta chỉ lưu trữ hai hàng của bảng DP gốc: hàng i-1 và hàng i. Khi tính toán xong hàng i, nó sẽ trở thành hàng i-1 cho bước tiếp theo (tính hàng i+1). Bằng cách này, chúng ta chỉ cần không gian O(min(m, n)) (chọn chiều nhỏ hơn để làm kích thước của vector 1 chiều).
Chúng ta có thể sử dụng hai vector 1 chiều, hoặc một vector 1 chiều với một biến tạm để lưu giá trị dp[i-1][j-1]. Cách dùng một vector và biến tạm gọn gàng hơn.
Giả sử n <= m (nếu không, ta đổi chỗ hai chuỗi để n là chiều nhỏ hơn). Ta dùng một vector dp kích thước n+1. dp[j] sẽ lưu trữ giá trị dp[i-1][j] ở đầu vòng lặp trong, và được cập nhật thành dp[i][j] cuối vòng lặp trong.
#include <vector> // Cần thiết cho std::vector
#include <string> // Cần thiết cho std::string
#include <algorithm> // Cần thiết cho std::max
int longestCommonSubsequence_o_min(const std::string& text1, const std::string& text2) {
int m = text1.length();
int n = text2.length();
// Đảm bảo n là chiều nhỏ hơn để tối ưu tốt nhất (O(min(m,n)) space)
// Bằng cách này, vector dp sẽ có kích thước min(m,n) + 1.
if (m < n) {
return longestCommonSubsequence_o_min(text2, text1);
}
// Sau swap (nếu có), text1 dài hơn hoặc bằng text2.
// dp vector sẽ có kích thước n+1, tương ứng với chiều của text2.
std::vector<int> dp(n + 1, 0); // dp[j] sẽ lưu trữ dp[i][j] cho hàng hiện tại i,
// nhưng khi bắt đầu vòng lặp j, nó đang lưu dp[i-1][j]
// Duyệt qua từng ký tự của text1 (đại diện cho các hàng i từ 1 đến m)
for (int i = 1; i <= m; ++i) {
// prev_top_left cần lưu giá trị dp[i-1][j-1] từ BƯỚC TRƯỚC CỦA VÒNG LẶP J
// Cho j=1, giá trị này là dp[i-1][0], luôn bằng 0.
int prev_top_left = 0;
// Duyệt qua từng ký tự của text2 (đại diện cho các cột j từ 1 đến n)
for (int j = 1; j <= n; ++j) {
// Lưu lại giá trị dp[i-1][j] TRƯỚC khi cập nhật dp[j] cho hàng i
int current_dp_j_before_update = dp[j]; // Đây chính là dp[i-1][j]
if (text1[i - 1] == text2[j - 1]) {
// Nếu ký tự khớp: dp[i][j] = dp[i-1][j-1] + 1
// dp[i-1][j-1] chính là giá trị prev_top_left
dp[j] = prev_top_left + 1;
} else {
// Nếu ký tự không khớp: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
// dp[i-1][j] chính là current_dp_j_before_update
// dp[i][j-1] chính là giá trị dp[j-1] SAU khi nó đã được cập nhật
// trong bước lặp j-1 của vòng lặp trong
dp[j] = std::max(current_dp_j_before_update, dp[j - 1]);
}
// Cập nhật prev_top_left cho BƯỚC LẶP J+1
// prev_top_left của j+1 cần giá trị dp[i-1][j], chính là current_dp_j_before_update
prev_top_left = current_dp_j_before_update;
}
// Sau khi vòng lặp j kết thúc, mảng dp hiện tại đã được cập nhật
// hoàn toàn để biểu diễn hàng i của bảng DP gốc.
// Trong lần lặp ngoài tiếp theo (i+1), mảng dp này sẽ được sử dụng
// làm "hàng trước đó".
}
return dp[n]; // Kết quả cuối cùng là dp[m][n], được lưu trữ ở dp[n] sau vòng lặp cuối cùng
}
Giải thích: Chúng ta sử dụng một vector dp kích thước O(min(m, n)). Vòng lặp ngoài duyệt qua một trong hai chuỗi (chuỗi dài hơn sau khi swap), tương ứng với việc duyệt các hàng của bảng DP 2D gốc. Vòng lặp trong duyệt qua chuỗi còn lại, tương ứng với các cột. Biến prev_top_left được sử dụng để lưu giá trị dp[i-1][j-1] trước khi ô dp[j-1] trong vector 1D bị cập nhật cho hàng i. Kỹ thuật này cho phép tính toán chính xác dp[i][j] chỉ với một vector 1D duy nhất, giảm không gian từ O(m*n) xuống O(min(m, n)).
Ví dụ 5: Khoảng cách chỉnh sửa tối thiểu (Edit Distance)
Bài toán: Cho hai chuỗi word1 và word2. Tìm số lần thao tác chỉnh sửa (chèn, xóa, thay thế) ít nhất để biến word1 thành word2.
QHĐ thông thường (Không gian O(m * n))
Gọi m là độ dài word1, n là độ dài word2.
Gọi dp[i][j] là khoảng cách chỉnh sửa tối thiểu để biến word1[0...i-1] thành word2[0...j-1].
Công thức truy hồi:
- Nếu
word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1](ký tự cuối cùng khớp, không cần thao tác ở đây). - Nếu
word1[i-1] != word2[j-1]:dp[i][j] = 1 + min(dp[i-1][j], // Xóa ký tựword1[i-1]` (tức là biến word1[0...i-2] thành word2[0...j-1])
Lấy minimum của 3 trường hợp và cộng thêm 1 thao tác.dp[i][j-1], // Chèn ký tự `word2[j-1]` (tức là biến word1[0...i-1] thành word2[0...j-2] rồi chèn thêm) dp[i-1][j-1])` // Thay thế ký tự `word1[i-1]` bằng `word2[j-1]` (tức là biến word1[0...i-2] thành word2[0...j-2] rồi thay)
Điều kiện cơ sở:
dp[0][0] = 0: Biến chuỗi rỗng thành chuỗi rỗng cần 0 thao tác.dp[i][0] = i: Biếnword1[0...i-1]thành chuỗi rỗng cầnilần xóa.dp[0][j] = j: Biến chuỗi rỗng thànhword2[0...j-1]cầnjlần chèn.
#include <vector>
#include <string>
#include <algorithm> // Cần thiết cho std::min
int minDistance_omn(const std::string& word1, const std::string& word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j]: min distance between word1[0...i-1] and word2[0...j-1]
// Kích thước (m+1) x (n+1)
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
// Base cases
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
// Ký tự cuối khớp, khoảng cách bằng dp[i-1][j-1]
dp[i][j] = dp[i - 1][j - 1];
} else {
// Ký tự cuối không khớp, 1 thao tác + min của 3 trường hợp
dp[i][j] = 1 + std::min({dp[i - 1][j], // Xóa word1[i-1]
dp[i][j - 1], // Chèn word2[j-1]
dp[i - 1][j - 1]}); // Thay thế word1[i-1]
}
}
}
return dp[m][n]; // Kết quả cuối cùng
}
Giải thích: Bảng dp 2 chiều kích thước (m+1) x (n+1). Tính dp[i][j] dựa vào các giá trị ở hàng i-1 và cột j-1 (dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). Không gian O(m * n).
Tối ưu không gian (Không gian O(min(m, n)))
Tương tự LCS, để tính hàng i, chúng ta chỉ cần thông tin từ hàng i-1 và các giá trị đã tính trên hàng i ở các cột trước đó. Chúng ta có thể sử dụng một vector 1 chiều và biến tạm để mô phỏng bảng DP 2D.
Giả sử n <= m (đổi chỗ nếu cần). Ta dùng một vector dp kích thước n+1. dp[j] sẽ lưu trữ giá trị dp[i-1][j] ở đầu vòng lặp trong, và được cập nhật thành dp[i][j] cuối vòng lặp trong.
#include <vector>
#include <string>
#include <algorithm> // Cần thiết cho std::min
int minDistance_o_min(const std::string& word1, const std::string& word2) {
int m = word1.length();
int n = word2.length();
// Đảm bảo n là chiều nhỏ hơn để tối ưu tốt nhất (O(min(m,n)) space)
// Bằng cách này, vector dp sẽ có kích thước min(m,n) + 1.
if (m < n) {
return minDistance_o_min(word2, word1);
}
// Sau swap (nếu có), word1 dài hơn hoặc bằng word2.
// dp vector sẽ có kích thước n+1, tương ứng với chiều của word2.
std::vector<int> dp(n + 1); // dp[j] sẽ lưu trữ dp[i][j] cho hàng hiện tại i,
// nhưng khi bắt đầu vòng lặp j, nó đang lưu dp[i-1][j]
// Base case cho hàng 0: dp[0][j] = j
// Khởi tạo vector dp ban đầu để biểu diễn hàng 0
for (int j = 0; j <= n; ++j) {
dp[j] = j;
}
// Duyệt qua từng ký tự của word1 (đại diện cho các hàng i từ 1 đến m)
for (int i = 1; i <= m; ++i) {
// Base case cho cột 0 của hàng i: dp[i][0] = i.
// Trong mảng 1D, giá trị này là dp[0] ở ĐẦU mỗi vòng lặp i.
// Lưu trữ giá trị dp[i-1][0] (trước khi cập nhật dp[0] cho hàng i)
int prev_top_left = dp[0]; // Lưu dp[i-1][0] (cho j=1, prev_top_left = dp[i-1][0])
dp[0] = i; // Cập nhật dp[0] thành dp[i][0]
// Duyệt qua từng ký tự của word2 (đại diện cho các cột j từ 1 đến n)
for (int j = 1; j <= n; ++j) {
// Lưu lại giá trị dp[i-1][j] TRƯỚC khi cập nhật dp[j] cho hàng i
int current_dp_j_before_update = dp[j]; // Đây chính là dp[i-1][j]
if (word1[i - 1] == word2[j - 1]) {
// Nếu ký tự khớp: dp[i][j] = dp[i-1][j-1]
// dp[i-1][j-1] chính là giá trị prev_top_left
dp[j] = prev_top_left;
} else {
// Nếu ký tự không khớp: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
// dp[i-1][j] chính là current_dp_j_before_update
// dp[i][j-1] chính là giá trị dp[j-1] SAU khi nó đã được cập nhật (dp[i][j-1])
// dp[i-1][j-1] chính là prev_top_left
dp[j] = 1 + std::min({current_dp_j_before_update, dp[j - 1], prev_top_left});
}
// Cập nhật prev_top_left cho BƯỚC LẶP J+1
// prev_top_left của j+1 cần giá trị dp[i-1][j], chính là current_dp_j_before_update
prev_top_left = current_dp_j_before_update;
}
// Sau khi vòng lặp j kết thúc, mảng dp hiện tại đã được cập nhật
// hoàn toàn để biểu diễn hàng i của bảng DP gốc.
// Trong lần lặp ngoài tiếp theo (i+1), mảng dp này sẽ được sử dụng
// làm "hàng trước đó".
}
return dp[n]; // Kết quả cuối cùng là dp[m][n], được lưu trữ ở dp[n] sau vòng lặp cuối cùng
}
Giải thích: Tương tự LCS, chúng ta sử dụng một vector 1 chiều dp kích thước O(min(m, n)). Vòng lặp ngoài duyệt qua một trong hai chuỗi (chuỗi dài hơn sau khi swap), tương ứng với việc duyệt các hàng của bảng DP 2D gốc. Vòng lặp trong duyệt qua chuỗi còn lại, tương ứng với các cột. Biến prev_top_left được sử dụng để lưu giá trị dp[i-1][j-1] trước khi ô dp[j-1] trong vector 1D bị cập nhật cho hàng i. Điều này cho phép tính toán chính xác dp[i][j] chỉ với một vector 1D duy nhất, giảm không gian từ O(m*n) xuống O(min(m, n)). Đặc biệt lưu ý cách xử lý base case dp[i][0] ở đầu mỗi vòng lặp i.
Bài tập ví dụ:
Xâu con chung dài nhất của 3 xâu.
Cho ba xâu ký tự X, Y, Z. Nhiệm vụ của bạn là tìm độ dài dãy con chung dài nhất có mặt trong cả ba xâu.
Input Format
Nhập vào 3 dòng lần lượt chứa X, Y, Z.(1<=len(X), len(Y), len(Z) <= 120)
Constraints
.
Output Format
In ra độ dài của xâu con chung dài nhất của 3 xâu.
Ví dụ:
Dữ liệu vào
MDJDJFHEHUEUYTY
CWAAJCJTUEITWKDM
IUYTREDCVBJHDZSSDữ liệu ra
2Bài toán này là một dạng mở rộng của bài toán tìm "Xâu con chung dài nhất" (Longest Common Subsequence - LCS) cho hai xâu lên ba xâu.
Hướng giải quyết phổ biến và hiệu quả là sử dụng Quy hoạch động (Dynamic Programming).
Định nghĩa trạng thái: Sử dụng một mảng 3 chiều
dp[i][j][k].dp[i][j][k]sẽ lưu trữ độ dài của xâu con chung dài nhất của:- Tiền tố độ dài
icủa xâu X (các ký tự từ X[0] đến X[i-1]). - Tiền tố độ dài
jcủa xâu Y (các ký tự từ Y[0] đến Y[j-1]). - Tiền tố độ dài
kcủa xâu Z (các ký tự từ Z[0] đến Z[k-1]).
- Tiền tố độ dài
Kích thước mảng DP: Kích thước của mảng DP sẽ là
(len(X)+1) x (len(Y)+1) x (len(Z)+1).Trường hợp cơ sở: Các giá trị tại biên của mảng DP sẽ là 0. Tức là,
dp[i][j][0] = dp[i][0][k] = dp[0][j][k] = 0cho mọii, j, k. Điều này có nghĩa là LCS của bất kỳ tập hợp xâu nào chứa ít nhất một xâu rỗng đều có độ dài bằng 0.Công thức truy hồi: Duyệt qua tất cả các bộ chỉ số
(i, j, k)từ(1, 1, 1)đến(len(X), len(Y), len(Z)). Tại mỗi trạng tháidp[i][j][k], xét ký tự cuối cùng của ba tiền tố đang xét:X[i-1],Y[j-1], vàZ[k-1].- Nếu
X[i-1] == Y[j-1] == Z[k-1]: Ba ký tự cuối cùng này khớp nhau và có thể là một phần của LCS. Do đó, độ dài LCS tăng thêm 1 so với LCS của ba tiền tố ngắn hơn (bỏ đi ký tự cuối cùng của mỗi xâu).dp[i][j][k] = dp[i-1][j-1][k-1] + 1 - Nếu các ký tự cuối cùng không đồng thời khớp nhau: Ít nhất một trong ba ký tự cuối cùng không thể là phần tử cuối cùng của LCS (vì nó không xuất hiện ở cả ba xâu tại vị trí tương ứng). Để tìm LCS dài nhất, ta phải xét các trường hợp bỏ qua ký tự cuối cùng của một trong các xâu và lấy giá trị lớn nhất:
dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
- Nếu
Kết quả cuối cùng: Sau khi lấp đầy mảng DP, giá trị tại
dp[len(X)][len(Y)][len(Z)]chính là độ dài của xâu con chung dài nhất của cả ba xâu X, Y, Z.
Độ phức tạp: Với độ dài các xâu tối đa 120, kích thước mảng DP là khoảng 121^3, và mỗi ô được tính trong thời gian hằng số. Do đó, độ phức tạp thời gian là O(len(X) len(Y) len(Z)), phù hợp với giới hạn bài toán.
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