Quy hoạch động 7.4: Palindromes và Các bài toán QHĐ liên quan
I. Những bài toán cơ sở
Trong Lập trình thi đấu, xâu palindrome (xâu đối xứng) là một loại xâu kí tự đặc biệt. Đó là những xâu mà viết xuôi hay viết ngược đều giống nhau, chẳng hạn như ABBA
hay TOEICCIEOT
,...Nhờ tính chất đặc biệt này, người ta phát triển ra rất nhiều bài toán liên quan tới xâu palindrome, không chỉ ở trong xâu kí tự mà còn có thể phát triển sang các bài tập trên dãy số, nhưng chủ yếu là dạng bài tập Quy hoạch động.
Trong chuyên đề này, tôi sẽ giới thiệu tới các bạn một số bài tập như vậy. Nhưng trước hết ta hãy cùng đến với những bài toán cơ sở trước đã.
1. Kiểm tra xâu palindrome
Đề bài
Cho một xâu kí tự độ dài . Kiểm tra xem xâu đó có phải xâu palindrome không?
Input:
- Dòng đầu tiên chứa số nguyên dương - số lượng test cases.
- Chứa duy nhất xâu kí tự độ dài .
Ràng buộc:
- .
- .
Output:
- In ra
Yes
nếu xâu đối xứng, ngược lại in raNo
. Kết quả của mỗi test case in ra trên một dòng.
Sample Input:
2
ABA
TOEIC
Sample Output:
Yes
No
Ý tưởng
Đây là một bài tập đơn giản mà bạn nào cũng phải làm qua khi mới bắt đầu học về xâu kí tự trong lập trình. Mặc dù vậy, tôi vẫn nói tới bài toán này vì ở những bài tập tiếp theo, chúng ta sẽ dùng nhiều tới việc kiểm tra tính đối xứng của một xâu.
Giả sử ta đánh số thứ tự của các kí tự trong xâu từ và kết thúc tại . Một xâu là đối xứng khi và chỉ khi nó thỏa mãn điều kiện:
Vậy ta kiểm tra bằng một vòng lặp, độ phức tạp .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
bool is_palin(string &s)
{
int n = s.size();
for (int i = 0; i <= (n - 1) / 2; ++i)
if (s[i] != s[n - i - i])
return false;
return true;
}
main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
if (is_palin(s))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
Ngôn ngữ Python:
def is_palin(s):
n = len(s)
for i in range((n - 1) / 2 + 1):
if s[i] != s[n - i - 1]:
return False
return True
if __name__ == '__main__':
t = int(input())
for _ in range(t):
s = input()
if is_palin(s):
print(Yes)
else:
print(No)
2. Xâu con palindrome dài nhất
Đề bài
Cho một xâu độ dài . Hãy xác định độ dài xâu con đối xứng dài nhất trong
Input:
- Một dòng duy nhất chứa xâu kí tự độ dài .
Ràng buộc:
- .
Output:
- In ra độ dài của xâu con đối xứng dài nhất tìm được trong .
Sample Input:
abcddcbfgh
Sample Output:
6
Ý tưởng
Cách làm duyệt mọi xâu con trong xâu ban đầu rồi kiểm tra tính đối xứng của từng xâu, chắc chắn không thể thỏa mãn yếu tố thời gian thực thi nên ta sẽ không bàn tới nữa.
Bài toán này có nhiều cách tiếp cận với những độ phức tạp khác nhau, nhưng ở đây tôi sẽ hướng dẫn các bạn hướng tiếp cận đơn giản nhất với độ phức tạp là là quy hoạch động.
Gọi là mảng đánh dấu xâu con có phải xâu đối xứng hay không: nếu xâu con đối xứng, ngược lại thì .
Xét cặp kí tự ta xây dựng công thức truy hồi để tính như sau:
-
Nếu thì xâu con có đối xứng hay không sẽ phụ thuộc vào xâu con . Thiết lập công thức:
-
Nếu hiển nhiên xâu con không đối xứng, ta có công thức:
Về cơ sở quy hoạch động, dễ dàng nhận ra:
- Xâu con có kí tự luôn luôn là đối xứng: .
- Xâu con có kí tự đối xứng hay không tùy vào hai kí tự đó: nếu .
Cuối cùng kết quả sẽ là với các căp thỏa mãn .
Độ phức tạp của cách này là .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
main()
{
string s;
cin >> s;
s = ' ' + s;
int n = s.size() - 1;
vector < vector < int > > palin(n + 1, vector < int >(n + 1, 0));
// Cơ sở quy hoạch động.
for (int i = 1; i <= n; ++i)
{
palin[i][i] = 1;
if (i < n)
palin[i][i + 1] = (a[i] == a[i + 1]);
}
// Tính bảng phương án.
for (int j = n; j >= 3; --j)
for (int i = 1; i <= j - 2; ++i)
palin[i][j] = (palin[i + 1][j - 1] & (s[i] == s[j]));
// Tìm kết quả cuối cùng.
int res = 0;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
if (palin[i][j])
res = max(res, j - i + 1);
cout << res;
}
Ngôn ngữ Python:
if __name__ == '__main__':
s = ' ' + input()
n = len(s) - 1
# Cơ sở quy hoạch động.
palin = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
palin[i][i] = 1
if i < n:
palin[i][i + 1] = 1 if s[i] = s[i + 1] else 0
# Tính bảng phương án.
for j in range(n, 2, -1):
for i in range(1, j - 1):
palin[i][j] = (palin[i + 1][j - 1] and s[i] == s[j])
# Tìm kết quả cuối cùng.
res = 0
for i in range(1, n + 1):
for j in range(i, n + 1):
if palin[i][j]:
res = max(res, j - i + 1)
print(res)
II. Một số bài toán khác liên quan
1. Chia xâu thành các Palindromes
Đề bài
Cho một xâu độ dài . Hãy tìm cách chia nó thành một số ít nhất các xâu con liên tiếp, sao cho mỗi xâu con đều là một palindrome?
Input:
- Một dòng duy nhất chứa xâu kí tự độ dài .
Ràng buộc:
- .
Output:
- Một số nguyên duy nhất là số lượng đoạn tối thiểu chia được.
Sample Input:
abacc
Sample Output:
2
Giải thích:
Chia xâu ban đầu thành xâu con đối xứng là aba
và cc
.
Ý tưởng
Coi rằng xâu ban đầu được đánh số kí tự từ vị trí .
Vẫn sử dụng quy hoạch động, ta sẽ gọi là số lượng xâu con đối xứng tối thiểu chia được từ xâu . Công thức được thiết lập khá đơn giản: Nếu như đoạn là một xâu đối xứng thì có thể gán bằng . Mà ta mong muốn kết quả nhỏ nhất, vì thế:
<center>
với xâu con là đối xứng
</center>Đến đây, công việc còn lại là kiểm tra một xâu con có phải đối xứng hay không. Nếu như sử dụng lại vòng lặp, thì độ phức tạp thuật toán sẽ là không thể đáp ứng giới hạn . Thay vào đó, ta sẽ khởi tạo trước một mảng giống như bài toán trước để xác định đoạn có phải là một xâu đối xứng hay không bằng hai vòng lặp. Sau đó, giải thuật sẽ trở thành:
Cơ sở quy hoạch động khởi tạo . Riêng .
Độ phức tạp giải thuật lúc này giảm xuống .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
vector < vector < int > > data_preparation(string &s, int n)
{
vector < vector < int > > palin(n + 1, vector < int >(n + 1, 0));
for (int i = 1; i <= n; ++i)
{
palin[i][i] = 1;
if (i < n)
palin[i][i + 1] = (s[i] == s[i + 1]);
}
for (int j = n; j >= 3; --j)
for (int i = 1; i <= j - 2; ++i)
palin[i][j] = (palin[i + 1][j - 1] & (s[i] == s[j]));
return palin;
}
void solution(int n, vector < vector < int > > &palin)
{
vector < int > dp(n + 1, 1001);
dp[1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = i - 1; j >= 0; --j)
if (palin[j + 1][i])
dp[i] = min(dp[i], dp[j] + 1);
cout << dp[n];
}
main()
{
string s;
cin >> s;
s = ' ' + s;
int n = s.size() - 1;
vector < vector < int > > palin = data_preparation(s, n);
solution(n, palin);
}
Ngôn ngữ Python:
def data_preparation(s, n):
palin = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
palin[i][i] = 1
if i < n:
palin[i][i + 1] = 1 if s[i] = s[i + 1] else 0
for j in range(n, 2, -1):
for i in range(1, j - 1):
palin[i][j] = (palin[i + 1][j - 1] and s[i] == s[j])
return palin
def solution(s, n, palin):
dp = [1001] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(0, i):
if palin[j + 1][i]:
dp[i] = min(dp[i], dp[j] + 1)
print(dp[n])
if __name__ == '__main__':
s = ' ' + input()
n = len(s) - 1
palin = data_preparation(s, n)
solution(n, palin)
2. Đếm số xâu con là Palindrome
Đề bài
Cho một xâu kí tự độ dài . Ở đây, ta định nghĩa "xâu con" của là một hoặc một số kí tự không cần liên tiếp nhau của giữ nguyên thứ tự của chúng trong xâu ban đầu.
Hãy đếm số lượng "xâu con" là đối xứng của
Input:
- Một dòng duy nhất chứa xâu kí tự độ dài .
Ràng buộc:
- .
Output:
- In ra một số nguyên là số lượng xâu con đối xứng của . Do kết quả có thể rất lớn, chỉ cần in ra phần dư của kết quả sau khi chia cho .
Sample Input:
IOICAMP
Sample Output:
9
Giải thích:
Các xâu con đối xứng là: I
, O
, I
, C
, A
, M
, P
, II
, IOI
.
Ý tưởng
Ý tưởng của bài tập này là sử dụng quy hoạch động. Ta nhận ra bài toán có bản chất đệ quy, bởi nếu coi là số xâu con đối xứng trong đoạn vị trí của thì ta xây dựng được công thức truy hồi như sau:
-
Nếu thì số lượng xâu con đối xứng của đoạn chỉ phụ thuộc vào số lượng xâu con đối xứng của đoạn và . Ngoài ra, ta lại phải trừ bớt đi số lượng xâu con bị trùng lặp hai lần tính trong đoạn . Tức là:
-
Nếu thì số lượng xâu con đối xứng của của đoạn sẽ có thêm một xâu là đồng thời cũng cộng với số lượng xâu con đối xứng ở giữa gộp từ hai đoạn và trừ bớt đi số lượng xâu con bị trùng lặp hai lần tính trong đoạn . Tuy nhiên, cần lưu ý rằng, bây giờ mỗi xâu con đối xứng trong đoạn lại có thể tạo thành thêm một xâu con đối xứng nữa bằng cách ghép và vào hai đầu xâu đó. Vì thế, ta có công thức:
Cơ sở quy hoạch động của bài toán là - mọi đoạn độ dài đều chỉ có xâu con đối xứng. Kết quả cuối cùng dĩ nhiên là .
Bằng hai vòng lặp, ta có thể tính được bảng phương án trong . Lưu ý cần kết hợp với đồng dư để đưa ra được kết quả đề bài yêu cầu.
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
void solution(string &s, int n)
{
vector < vector < int > > dp(n + 1, vector < int >(n + 1));
for (int i = 1; i <= n; ++i)
dp[i][i] = 1;
for (int l = 2; l <= n; ++l)
for (int i = 1; i <= n - l + 1; ++i)
{
int j = i + l - 1;
dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod;
if (s[i] == s[j])
(dp[i][j] += 1) %= mod;
else
dp[i][j] = (dp[i][j] - dp[i + 1][j - 1] + mod) % mod;
}
cout << dp[1][n];
}
main()
{
string s;
cin >> s;
s = ' ' + s;
int n = s.size() - 1;
solution(s, n);
}
Ngôn ngữ Python:
def solution(s, n):
mod = 10**9 + 7
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][i] = 1
for l in range(2, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod
if s[i] == s[j]:
(dp[i][j] += 1) %= mod
else:
(dp[i][j] -= dp[i + 1][j - 1]) %= mod
print(dp[1][n])
if __name__ == '__main__':
s = ' ' + input()
n = len(s) - 1
solution(s, n)
3. Xóa xâu con
Đề bài
Cho xâu kí tự chỉ gồm các chữ cái latin in thường. Ở mỗi bước, bạn được phép chọn ra một xâu con liên tiếp của và xóa nó đi, với điều kiện xâu con đó phải là xâu đối xứng.
Hãy đếm số bước ít nhất để xóa toàn bộ xâu
Input:
- Dòng đầu tiên chứa số nguyên dương T – số lượng test cases.
- dòng tiếp theo, mỗi dòng chứa một xâu kí tự .
Ràng buộc:
- .
- với là độ dài xâu .
Output:
- In ra số lượng kí tự tối thiểu cần thêm vào.
Sample Input:
2
teen
aadcbcab
Sample Output:
3
4
Ý tưởng
Gọi là số thao tác tối thiểu để xóa đoạn của xâu .
Xét đoạn ta có:
-
Nếu như thì ta xóa hết đoạn đồng thời ở thao tác xóa cuối cùng, ta gộp luôn hai kí tự vào hai đầu của xâu đối xứng cuối cùng và xóa chung. Vì thế:
-
Còn nếu thì có thể tồn tại ba cách xóa:
- Xóa đoạn rồi mới xóa .
- Xóa đoạn rồi mới xóa .
- Xóa một đoạn đối xứng liên tiếp rồi xóa đoạn .
Ta rút ra công thức:
Về cơ sở quy hoạch động, ta có - cần một thao tác để xóa các xâu con độ dài và hoặc tùy thuộc vào có bằng hay không. Kết quả cuối cùng tất nhiên là .
Độ phức tạp: .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INFTY = 1e9 + 7;
void solution(string &s)
{
s = ' ' + s;
int n = s.size() - 1;
vector < vector < int > > dp(n + 1, vector < int >(n + 1, INFTY));
for (int i = 1; i <= n; ++i)
{
dp[i][i] = 1;
if (i < n)
dp[i][i + 1] = (s[i] == s[i + 1]) ? 1 : 2;
}
for (int len = 3; len <= n; ++len)
{
for (int i = 1; i <= n - len + 1; ++i)
{
int j = i + len - 1;
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1];
else
dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);
for (int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
cout << dp[1][n] << endl;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int ntest;
cin >> ntest;
while (ntest--)
{
string s;
cin >> s;
solution(s);
}
return 0;
}
Ngôn ngữ Python:
INFTY = 10**9 + 7
def solution(s):
n = len(s) - 1
dp = [[INFTY] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][i] = 1
if i < n:
dp[i][i + 1] = 1 if s[i] == s[i + 1] else 2
for l in range(3, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
print(dp[1][n])
if __name__ == '__main__':
t = int(input())
for _ in range(t):
s = ' ' + input()
solution(s)
III. Tài liệu tham khảo
All Rights Reserved