C++で特定の文字列からk個の一意のサブシーケンスを見つけた後にコストを見つけるプログラム

文字列sと別の値kがあるとします。 k個の一意のサブシーケンスを取得できるように、sのいくつかのサブシーケンスを選択する必要があります。ここで、サブシーケンスを選択するコストは、（s）の長さ-（サブシーケンス）の長さに等しくなります。したがって、k個の一意のサブシーケンスを選択した後、可能な限り最小の総コストを見つける必要があります。このセットが見つからない場合は、-1を返します。空の文字列を有効なサブシーケンスと見なします。

したがって、入力がs ="pqrs"、k =4の場合、出力は3になります。

これを解決するには、次の手順に従います-

• n：=sのサイズ

• サイズ（n + 1）x（n + 1）の2D配列dpを1つ定義し、0で初期化します

• 最後に1つのマップを定義する

• dp [0、0]：=1

• 初期化i：=0の場合、i

  • dp [i + 1、0]：=1

  • 初期化j：=（i + 1）の場合、j> =1の場合、更新（jを1つ減らす）、実行-

    • dp [i + 1、j]：=dp [i、j] + dp [i、j-1]

  • s [i]がlastの終了要素でない場合、-

    • 初期化j：=0の場合、j <=last [s [i]]の場合、更新（jを1増やします）、実行-

      • dp [i + 1、j + 1]-=dp [last [s [i]]、j]

  • last [s [i]]：=i

• コスト：=0

• 初期化i：=nの場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • val：=kとdp[n、i]

    の最小値

  • コスト：=コスト+（val *（n --i））

  • k：=k-dp [n、i]

  • k <=0の場合、-

    • ループから出てきます

• k <=0の場合、-

  • 返品費用

• -1を返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int k) {
   int n = s.size();
   vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
   unordered_map<char, int> last;
   dp[0][0] = 1;
   for (int i = 0; i < n; i++) {
      dp[i + 1][0] = 1;
      for (int j = (i + 1); j >= 1; j--) {
         dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
      }
      if (last.find(s[i]) != last.end()) {
         for (int j = 0; j <= last[s[i]]; j++) {
            dp[i + 1][j + 1] -= dp[last[s[i]]][j];
         }
      }
      last[s[i]] = i;
   }
   int cost = 0;
   for (int i = n; i >= 0; i--) {
      int val = min(k, dp[n][i]);
      cost += (val * (n - i));
      k -= dp[n][i];
      if (k <= 0) {
         break;
      }
   }
   if (k <= 0) {
      return cost;
   }
   return -1;
}
int main(){
   cout << solve("pqrs",4) << endl;
   return 0;
}

入力：

"pqrs", 4

出力

3