【C++】隣接する文字のASCII値の差が1となる文字列の個数を動的計画法で求める

本記事では、整数 num が入力として与えられたとき、「隣接する文字同士のASCII値の差がちょうど1である」という条件を満たす長さ num の文字列の総数を、C++ の動的計画法（DP）を用いて効率的に求める方法を解説します。

例えば num が 2 の場合、条件を満たす文字列は「ab」「ba」「bc」「cb」……「yz」「zy」となります。

具体例

入力： num = 3

出力： 隣接する文字の差が1である文字列の個数 ― 98

説明： 条件を満たす文字列の例としては、「abc」「aba」「cde」……「xyx」「zyz」「xyz」などが挙げられます。

入力： num = 2

出力： 隣接する文字の差が1である文字列の個数 ― 50

説明： 条件を満たす文字列の例としては、「ab」「ba」「cd」……「xy」「zy」「yz」などが挙げられます。

解法のアプローチ

まず、長さが 2 の場合について考えてみましょう。

• a で始まる文字列：「ab」（1通り）
• b で始まる文字列：「ba」「bc」（2通り）
• c で始まる文字列：「cb」「cd」（2通り）……以下同様

次に、長さが n の場合への一般化を考えます。

• a で始まる文字列の数 ＝ b で始まる長さ n−1 の文字列の数
• b で始まる文字列の数 ＝ a または c で始まる長さ n−1 の文字列の数の合計
• c で始まる文字列の数 ＝ b または d で始まる長さ n−1 の文字列の数の合計

この漸化式の構造から、動的計画法によって問題を解くことができます。

DPテーブルの設計

2次元配列 arr[num+1][27] を用意し、arr[i][j] に「アルファベット j 番目（0 = 'a', 1 = 'b', …）から始まる長さ i の文字列の数」を格納します。

• 長さ 1 の文字列「a」「b」…「z」それぞれに対して arr[1][j] はすべて 1 になります。
• それ以外の arr[2〜num][0〜25] については、j = 0 のときは arr[i][j] = arr[i-1][j+1]、それ以外のときは arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1] と更新します。
• 最終的な答えは、num 行目の各要素の合計値です。

アルゴリズムの手順

• 整数 num を入力として受け取る。
• 関数 difference_strings(int num) が num を受け取り、条件を満たす文字列の個数を返す。
• 初期カウント count を 0 とする。
• 配列 arr[num + 1][27] をすべて 0 で初期化する。
• arr[1][0〜25] をすべて 1 で初期化する。
• 2つの for ループを用いて、行 2 から最終行まで、列 0 から 25 まで（26種類のアルファベット全体）を走査する。
• j = 0 の場合（開始文字が 'a'）：arr[i][j] = arr[i - 1][j + 1] を設定する。
• それ以外の場合：arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j + 1] を設定する。
• ループ完了後、最後の行を走査し、arr[num][0〜25] の値を count に加算する。
• count を結果として返す。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
    long int count = 0;
    long int arr[num + 1][27];
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i <= 25; i++){
        arr[1][i] = 1;
    }
    for (int i = 2; i <= num; i++){
        for (int j = 0; j <= 25; j++){
            if (j == 0){
                arr[i][j] = arr[i - 1][j + 1];
            }
            else{
                arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
            }
        }
    }
    for (int i = 0; i <= 25; i++){
        count = (count + arr[num][i]);
    }
    return count;
}
int main(){
    int num = 2;
    cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of strings where adjacent characters are of difference one are: 50

このように、動的計画法を活用することで、全ての文字列を列挙することなく、隣接する文字の差が1となる文字列の総数を O(num × 26) の計算量で効率的に求めることができます。