C++で異なる部分列の数を数える：動的計画法による解法

問題の概要

2つの文字列 S と T が与えられたとき、S の部分列のうち T と一致するものが何通りあるかを数えるのがこの問題です。

ここでいう部分列（subsequence）とは、元の文字列から一部の文字（0個でも可）を取り除いて作られる新しい文字列のことであり、残った文字の相対的な順序は崩れません。たとえば「ACE」は「ABCDE」の部分列ですが、「AEC」は元の順序が保たれていないため部分列ではありません。

たとえば、入力が「baalllloonnn」と「balloon」の場合、T に一致する S の部分列は 36 通り存在します。

解法の考え方（動的計画法）

この問題は動的計画法（DP）を使うことで効率的に解けます。dp[i][j] を「s の先頭 i 文字から作れる部分列のうち、t の先頭 j 文字と一致するものの個数」と定義します。

遷移のルールは次のとおりです。

• s[i] == t[j] のとき：その文字を使う場合が dp[i-1][j-1]、使わない場合が dp[i-1][j] なので、両者を足した値になります。
• s[i] != t[j] のとき：その文字は使えないため、dp[i][j] = dp[i-1][j] となります。
• 初期条件：t が空文字列のときは選び方が常に 1 通り（何も取らない）なので dp[i][0] = 1。逆に s が空で t が空でない場合は 0 になります。

アルゴリズムの手順

1. n := s の長さ、m := t の長さとし、添字の扱いを簡単にするため s と t の先頭に空白を付加します。
2. (n+1) × (m+1) のサイズの DP テーブルを作成します。
3. dp[0][0] := 1 とし、すべての行の 0 列目に 1 を設定します。
4. i を 1 から n まで、j を 1 から m まで二重ループで回します。
   • s[i] == t[j] ならば dp[i][j] := dp[i-1][j-1]
   • その後、dp[i][j] := dp[i][j] + dp[i-1][j]
5. 最終的に dp[n][m] を返します。

C++での実装例

以下が実際の C++ コードです。オーバーフロー対策として long long 型を使用しています。

#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

計算量

時間計算量は O(n × m)、空間計算量も DP テーブル分の O(n × m) です。なお、dp 配列を 1 次元に圧縮すれば、空間計算量を O(m) まで削減することも可能です。