C++ 中重复删除回文子串后删除字符串的最少步骤
c++server side programmingprogramming
问题描述
给定一个仅包含整数字符的字符串。我们需要用最少的步骤删除该字符串的所有字符，其中一步即可删除回文子串。删除子串后，剩余部分将连接起来。
示例
如果输入字符串为 3441213，则至少需要 2 个步骤
- 首先从字符串中删除 121。现在剩余的字符串是 3443
- 由于剩余字符串是回文串，因此删除它
算法
我们可以使用动态规划来解决这个问题
1. 令 dp[i][j] 表示删除子字符串 s[i, j] 所需的步数。 2. 每个字符将被单独删除，或作为某个子字符串的一部分被删除，因此在第一种情况下，我们将删除字符本身，并调用子问题 (i+1, j)。 3. 在第二种情况下，我们将迭代右侧当前字符的所有出现位置，如果 K 是此类出现的索引，则问题将简化为两个子问题 (i+1, K - 1) 和 (K+1, j)。 4. 我们可以得出这个子问题 (i+1, K-1)，因为我们只需删除相同的字符，然后调用中间子串 5. 我们需要考虑前两个字符相同的情况，这种情况下我们可以直接简化为子问题 (i+2, j)
示例
#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;
}
编译并执行上述程序，将生成以下输出
输出
Minimum required steps: 2
