プログラマ脳を鍛える数学パズル 17

今回はコードをみれば何がしたいか分かるかと

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

とまぁ愚直に再起すればよく、前回並んだ性別と、後何人並べるかで残りのパターン数は決定される（後述）ので、メモを取りながら再起すればいい。

例えば、男性スタートで 3 人並ぶとすれば、BBB, BGB, BBG, GBB, GBG の５通りだが、女性スタートなら BBB, BGB, BBG の 3 通りしか存在しない。
逆にそれより前が何人、どう並んでようと、このパターン数は変わらないので、直前に並んでいる男女と、残りの人数でパターン数が決定できる。

BOY = 'B'
GIRL = 'G'

n = 30
memo = {}


def add(current: list) -> int:
    counts = len(current)

    # 30 人並んだら終了
    if counts >= n:
        return 1

    # 前回並んだ人
    last = current[-1] if counts > 0 else 'N'

    # メモがあればそこから応答
    if (last, counts) in memo:
        return memo[(last, counts)]

    # 男女を繋げる
    cnt = 0
    for cur in [BOY, GIRL]:
        # 女性は連続して並べない
        if last == GIRL and cur == GIRL:
            continue
        # パターンをカウント
        cp = current[:]
        cp.append(cur)
        cnt += add(cp)

    # メモ化
    memo[(last, counts)] = cnt

    # カウント応答
    return cnt


print(add([]))