Hướng dẫn giải của Phân tích chuỗi thành Palindrom
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm cách phân tích một xâu ký tự cho trước thành một dãy các xâu con liên tiếp nhau sao cho mỗi xâu con trong dãy đều là một xâu Palindrome (đọc xuôi hay ngược đều giống nhau). Mục tiêu là tìm cách phân tích sử dụng số lượng palindrome ít nhất có thể. Ví dụ với xâu 'bobseesanna', cách phân tích tối ưu là 'bob' + 'sees' + 'anna' (3 phần tử), không thể ít hơn được nữa.
Các cách tiếp cận
Cách Quy hoạch động cơ bản
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
// dp[i] là số lượng palindrome ít nhất để phân tích xâu s[0...i]
vector<int> dp(n, n);
// Bước 1: Kiểm tra tất cả các xâu con có phải là palindrome không
vector<vector<bool>> isPal(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) isPal[i][i] = true; // Xâu độ dài 1
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
if (len == 2) isPal[i][j] = true;
else isPal[i][j] = isPal[i+1][j-1];
}
}
}
// Bước 2: Quy hoạch động
for (int i = 0; i < n; i++) {
if (isPal[0][i]) {
dp[i] = 1;
continue;
}
for (int j = 0; j < i; j++) {
// Nếu xâu s[j+1...i] là palindrome thì thử kết hợp
if (isPal[j+1][i]) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
cout << dp[n-1] << endl;
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Hướng tiếp cận này tách bài toán thành 2 bước:
- Precompute (tiền xử lý) một bảng 2 chiều để đánh dấu các xâu con palindrome. Bảng isPal[i][j] = true nếu s[i...j] là palindrome. Việc này mất O(n^2).
- Dùng mảng dp[] để lưu kết quả. dp[i] là đáp án cho xâu s[0...i]. Với mỗi vị trí i, ta duyệt qua tất cả các vị trí j < i, nếu s[j+1...i] là palindrome thì cập nhật dp[i] = min(dp[i], dp[j] + 1). Cách này đảm bảo tìm được kết quả tối ưu vì nó thử tất cả các cách phân tích có thể.
Cách Tối ưu hóa Quy hoạch động
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dp(256, vector<int>(256, 0));
vector<int> dp1(256, 1e7);
int main() {
string s;
cin >> s;
int n = s.length();
// Chuyển về 1-based index cho tiện thao tác
// dp[i][j] = 1 nếu s[i...j] là palindrome
for (int l = 1; l <= n; l++) {
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
if (l == 1) dp[i][j] = 1;
else if (l == 2) {
if (s[i-1] == s[i]) dp[i][j] = 1;
}
else {
// Dùng kết quả từ các xâu con ngắn hơn
if (s[i-1] == s[j-1] && dp[i+1][j-1]) dp[i][j] = 1;
}
}
}
// dp1[i] là số lượng palindrome ít nhất cho xâu độ dài i
dp1[0] = 0;
for (int i = 1; i <= n; i++) {
dp1[i] = i; // Khởi tạo giá trị lớn (phân tách từng ký tự)
for (int j = 0; j < i; j++) {
// Nếu đoạn j+1...i là palindrome
if (dp[j+1][i]) {
dp1[i] = min(dp1[i], dp1[j] + 1);
}
}
}
cout << dp1[n];
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Cách này tương tự cách 1 nhưng được tối ưu hóa về mặt code structure:
- Sử dụng mảng 2 chiều dp[][] để lưu trữ trạng thái palindrome.
- Sử dụng mảng dp1[] để lưu kết quả quy hoạch động.
- Logic xử lý giống hệt cách 1: Duyệt độ dài, kiểm tra palindrome, và cập nhật kết quả. Cách này thường có tốc độ chạy nhanh hơn do cách truy cập bộ nhớ và tổ chức vòng lặp tốt hơn.
Cách Quy hoạch động kết hợp (Optimized Space)
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
// dp[i] là số lượng palindrome ít nhất cho prefix s[0...i]
vector<int> dp(n, n);
// isPal[i][j] true nếu s[i...j] là palindrome
vector<vector<bool>> isPal(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
isPal[i][i] = true;
// Nếu xâu kí tự đơn, dp[i] có thể là 1
dp[i] = (i == 0 ? 1 : dp[i-1] + 1);
for (int j = 0; j <= i; j++) {
if (s[i] == s[j]) {
// Kiểm tra điều kiện palindrome
if (i - j < 2) {
isPal[j][i] = true;
} else {
isPal[j][i] = isPal[j+1][i-1];
}
// Nếu s[j...i] là palindrome
if (isPal[j][i]) {
if (j == 0) dp[i] = 1;
else dp[i] = min(dp[i], dp[j-1] + 1);
}
}
}
}
cout << dp[n-1] << endl;
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Đây là biến thể của thuật toán Manacher hoặc cách tiếp cận trung gian.
- Ta vẫn dùng bảng isPal để kiểm tra palindrome.
- Trong cùng một vòng lặp, ta vừa tính isPal[j][i] (dựa trên các kết quả trước đó) vừa cập nhật ngay dp[i] nếu tìm được một đoạn palindrome kết thúc tại i.
- Vòng lặp
ităng dần,jchạy từ 0 đếni. Điểm khác biệt là việc tính toánisPalvàdpđược lồng vào nhau, nhưng về tổng thể độ phức tạp vẫn là O(n^2).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(n^2) | Quy hoạch động cơ bản |
| 2 | O(n^2) | O(n^2) | Tối ưu hóa Quy hoạch động |
| 3 | O(n^2) | O(n^2) | Quy hoạch động kết hợp (Optimized Space) |
Bài học kinh nghiệm
- Bài toán có tính chất quy hoạch động: nghiệm tối ưu của bài toán lớn được tạo thành từ nghiệm tối ưu của bài toán con.
- Tiền xử lý (Precompute) các xâu con palindrome giúp giảm thời gian kiểm tra từ O(n) xuống O(1) trong bước quy hoạch động.
- Bài toán này có thể coi là tìm đường đi ngắn nhất trên đồ thị: các node là vị trí từ -1 đến n-1, có cạnh từ j đến i nếu s[j+1...i] là palindrome.
Lỗi thường gặp
- Sai sót trong việc quản lý chỉ số mảng (off-by-one error), đặc biệt khi chuyển đổi giữa 0-based và 1-based indexing.
- Quên xử lý trường hợp cơ bản: xâu độ dài 1 luôn là palindrome và cần 1 phần tử.
- Khởi tạo sai giá trị vô cùng (INF) quá nhỏ so với độ dài tối đa của xâu (n <= 255).
Bình luận