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

絡まない糸電話、再起にしてようやっと理解できた

def string_phone(N: int) -> int:
    def pair(n: int) -> int:
        if n < 2:
            print(f'pait:{n} -> 1')
            return 1
        ans = 0
        for i in range(1, n, 2):
            ans += pair(i-1) * pair(n - i - 1)

        print(f'pait:{n} -> {ans}')
        return ans
    return pair(N)


print(string_phone(6))

速度が欲しければメモ化すれば良いと思う。
手続きが理解できないマン

ans = N-2人パターン数x0人パターン数 + N-4人パターン数x2人パターン数... + 0人パターン数xN-2人パターン数

みたいな計算になる。
仮に 6 を当てはめると

6人パターン数 = pair(0)*pair(4) + pair(2)*pair(2) + pair(4)*pair(0) = 1*2 + 1*1 + 2*1=5

そう考えれば解答例にしたがって、事前に 2 で割った方が返って理解が早かったかもわからん