C++プログラミングの個別のサブシーケンス

文字列のサブシーケンスは、残りの文字の相対位置を乱すことなく、文字の一部（なしでもかまいません）を削除することによって元の文字列から形成される新しい文字列であることがわかっています。 （同様に、「ACE」は「ABCDE」のサブシーケンスですが、「AEC」はサブシーケンスではありません）。

入力文字列が「baalllloonnn」と「balloon」の場合、36通りの選択方法があります。

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

• n：=sのサイズ、m：=tのサイズ。 sとtの前に空白を連結して、sとtを更新します

• サイズ（n + 1）x（m + 1）の行列を1つ作成します

• dp [0、0]：=1を設定し、次にすべての行の0番目の列に1を設定し、1を入力します

• 1からnの範囲のiの場合

  • 1からmの範囲のjの場合

    • s [i] =t [j]の場合、

      • dp [i、j]：=dp [i – 1、j – 1]

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

• dp [n、m]

  を返します

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

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int numDistinct(string s, string t) {
      int n = s.size();
      int m = t.size();
      s = " " + s;
      t = " " + t;
      vector < vector <lli> > dp(n + 1, vector <lli> (m + 1));
      dp[0][0] = 1;
      for(int i = 1; i <= n; i++)dp[i][0] = 1;
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
            dp[i][j]+= dp[i - 1][j];
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

入力

"baalllloonnn"
"balloon"

出力

36