從字串 A 中刪除字元以移除任何作為字串 B 的子序列的最小成本

---

給定兩個字串 string A 和 string B，以及一個數組表示刪除給定字串 A 的第 i 個字元的成本。我們需要以最小成本刪除字串 A 的一些字元（可能為零或沒有），以使 A 的任何子序列都不表示字串 B。我們將看到三種實現程式碼的方法：遞迴方法；遞迴和備忘錄方法；以及表格化或迭代動態規劃。

示例

讓我們來看下面的例子：

輸入

string a = "xanxd"
string b = "xd" 
int cost[] = {1, 2, 3, 4, 5}

輸出

5

解釋

這裡我們需要從字串 A 中刪除所有出現的“xd”作為子序列，為此我們有兩種方法：我們可以從給定字串中刪除“d”，這將導致成本為 5；或者我們必須刪除兩者“x”，這又將花費 1 + 4，即 5。

遞迴方法

在這種方法中，我們將建立一個遞迴函式，該函式將採用兩個字串的當前索引和兩個字串作為引數，以及第二個字串中刪除的索引數。將有兩種不同的情況，並且兩者都分別處理。

如果兩個字串在任何位置的當前字元相同，那麼我們必須決定是刪除字串 A 的當前字元（給定成本），還是跳過它，並且不會更改已刪除的變數。

如果兩個字元不同，則不需要刪除，我們將直接移動到字串 A 的下一個字元。

示例

#include <bits/stdc++.h>
using namespace std;

// recursive function to get the required result 
int rec(string& a, string& b, int idx1, int idx2, vector<int>& cost, int rem){
   // base condition to check the edge cases 
   if(idx1 == 0 or idx2 == 0) {
      return rem == 0 ? 1e5:0;
   }	
   if(a[idx1 - 1] == b[idx2 - 1]){
      return min(cost[idx1-1] + rec(a,b, idx1-1, idx2, cost, rem), rec(a, b, idx1-1, idx2-1, cost, rem-1));
   } else {
      return rec(a, b, idx1-1, idx2, cost, rem);
   }
}
// function to get call to the recursive function 
int getCost(string a, string b, vector<int> cost){
   // calling to the recursive function 
   return rec(a, b, a.length(), b.length(), cost, b.length());
}
int main(){
   string a = "abccdabccdabccd"; // given string a
   string b = "bccd"; // given string b
   vector<int> cost = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; // given cost array    
   // calling to the function to get the result
   cout << "Minimum cost to delete characters from String A to remove any subsequence as String B is: " << getCost(a, b, cost);
   return 0;
}

輸出

Minimum cost to delete characters from String A to remove any subsequence as String B is: 21

時間和空間複雜度

上述程式碼的時間複雜度為 O(2^M)，其中 M 是給定第二個字串的大小。

上述程式碼的空間複雜度為 O(M)，因為我們正在進行遞迴呼叫，並且遞迴棧會佔用記憶體。

遞迴 + 備忘錄方法

在這種方法中，我們將儲存函式呼叫中已訪問狀態的結果，並且對於再次呼叫該函式，將返回該值，這將時間複雜度從指數減少到二次。讓我們看看程式碼以便更好地理解：

示例

#include <bits/stdc++.h>
using namespace std;

int memo[105][105][3]; // array to store results 
// recursive function to get the required result 
int rec(string& a, string& b, int idx1, int idx2, vector<int>& cost, int rem){
   // base condition to check the edge cases 
   if(idx1 == 0 or idx2 == 0) {
      return rem == 0 ? 1e5:0;
   }	
   int state = rem > 0 ? 1 : 0;
   if(memo[idx1][idx2][state] != -1){
      return memo[idx1][idx2][state]; 
   }
   if(a[idx1 - 1] == b[idx2 - 1]){
      memo[idx1][idx2][state] = min(cost[idx1-1] + rec(a,b, idx1-1, idx2, cost, rem), rec(a, b, idx1-1, idx2-1, cost, rem-1));
      return memo[idx1][idx2][state]; 
   } else {
      memo[idx1][idx2][state] = rec(a, b, idx1-1, idx2, cost, rem);
      return memo[idx1][idx2][state]; 
   }
}
// function to get call to the recursive function 
int getCost(string a, string b, vector<int> cost){
   memset(memo, -1, sizeof(memo));
   // calling to the recursive function 
   return rec(a, b, a.length(), b.length(), cost, b.length());
}
int main(){
   string a = "abccdabccdabccd"; // given string a
   string b = "bccd"; // given string b
   vector<int> cost = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; // given cost array   
   // calling to the function to get the result
   cout << "Minimum cost to delete characters from String A to remove any subsequence as String B is:" << getCost(a, b, cost);
   return 0;
}

輸出

Minimum cost to delete characters from String A to remove any subsequence as String B is: 21

時間和空間複雜度

上述程式碼的時間複雜度為 O(N*M)，其中 M 是給定第二個字串的大小，N 是第一個字串的大小。

上述程式碼的空間複雜度為 O(N*M)，因為我們使用的是一個 3 維陣列（大約為 N*M 大小）。

結論

在本教程中，我們實現了一個問題，以查詢從給定字串 A 中刪除字元以移除任何作為給定字串 B 的子序列的最小成本。其中字串 A 的每個字元的成本也給出。首先，我們實現了一種遞迴方法，然後我們將其更新為一種備忘錄方法，其中我們儲存已訪問狀態的結果並存儲在一個數組中以減少時間複雜度。