ユニークビジョンプログラミングコンテスト2022 (AtCoder Beginner Contest 248) F - Keep Connect (500)
$ dp[i][j][k]] で$ i列目まで見て$ j回取り除いて上下が分離されているかどうかの場合の数を表す
初期値は$ dp[0][0][0] = dp[0][1][1] = 1
$ i \ge 1の場合の遷移は以下のとおり
$ dp[i][j+2][1] = dp[i][j+2][1] + 2 dp[i-1][j][0]
上と中央、下と中央を消す場合の2通り
$ dp[i][j+1][0] = dp[i][j+1][0] + 3dp[i-1][j][0]
上、中央、下を消す場合の3通り
$ dp[i][j+1][1] = dp[i][j+1][1] + dp[i-1][j][1]
中央以外を消すと分断が修復不可なので1通り
$ dp[i][j][0] = dp[i][j][0] + dp[i-1][j][0] + dp[i-1][j][1]
消さなければそれまでの状態に関わらず上下が繋がる
必要な$ i について$ dp[n-1][i][0] を表示すれば良い