$dp[i][val]$ を，$B_i = val$ としたときに，$B_i, B_{i + 1}, \cdots, B_N$の部分において，$B_j = B_{j + 1}$ となる $j$ の個数としてありうる値の集合とします．

まず，公式解説の考察により，$val$ として考えるのは $1, 2$ で良いです．また，集合を set でそのまま持つとデータ量が多いので，ありうる値を区間の集合として保持します．さらに，偶数と奇数で分けて保持します．

データ量が少ないと予想して実装すると，この問題に正解することができます．計算量は \(O(N)\) です．