Tuyên bố vấn đề
Cho một chuỗi chỉ chứa các ký tự dưới dạng số nguyên. Chúng ta cần xóa tất cả ký tự của chuỗi này trong một số bước tối thiểu mà trong một bước, chúng ta có thể xóa chuỗi con là palindrome. Sau khi xóa một chuỗi con, các phần còn lại được nối với nhau.
Ví dụ
Nếu chuỗi đầu vào là 3441213 thì cần tối thiểu 2 bước
- Đầu tiên, hãy xóa 121 khỏi chuỗi. Bây giờ chuỗi còn lại là 3443
- Xóa chuỗi còn lại vì đó là palindrome
Thuật toán
Chúng ta có thể sử dụng lập trình động để giải quyết vấn đề này
1. Let dp[i][j] denotes the number of steps it takes to delete the substring s[i, j] 2. Each character will be deleted alone or as part of some substring so in the first case we will delete the character itself and call subproblem (i+1, j) 3. In the second case we will iterate over all occurrence of the current character in right side, if K is the index of one such occurrence then the problem will reduce to two subproblems (i+1, K – 1) and (K+1, j) 4. We can reach to this subproblem (i+1, K-1) because we can just delete the same character and call for mid substring 5. We need to take care of a case when first two characters are same in that case we can directly reduce to the subproblem (i+2, j)
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
int n = str.length();
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
}
}
for (int len = 1; len <= n; len++) {
for (int i = 0, j = len - 1; j < n; i++, j++) {
if (len == 1)
dp[i][j] = 1;
else {
dp[i][j] = 1 + dp[i + 1][j];
if (str[i] == str[i + 1]) {
dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
}
for (int K = i + 2; K <= j; K++){
if (str[i] == str[K]) {
dp[i][j] =
min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
}
}
}
}
}
return dp[0][n - 1];
}
int main() {
string str = "3441213";
cout << "Minimum required steps: " <<
getMinRequiredSteps(str) << endl;
return 0;
} Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau
Đầu ra
Minimum required steps: 2