資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究刪除字串的最少步驟，且在 C++ 中重複刪除迴文子串
問題陳述
給定一個只包含整數的字串。我們需要以最少的步驟刪除該字串中的所有字元，在一步中，我們可以刪除構成迴文的子字串。刪除子字串後，剩餘部分將進行連線。
示例
如果輸入字串為 3441213，則需要最少 2 步
- 首先從字串中刪除 121。現在剩下的字串是 3443
- 刪除剩餘字串，因為它是一個迴文
演算法
我們可以使用動態規劃來解決這個問題
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)
示例
#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
更新於： 23-Dec-2019
818 次瀏覽
廣告