No.036 C

DP である.

$i$ 番目まで見たときに, 区間 $[*, i]$ の1の数-0の数の最大値が $j$, 最小値が $k$ である組み合わせの数を $C(i, j, k)$ とする.

$i$ 番目が 0 のとき:

$$C(i, j-1, k-1) \leftarrow C(i-1, j, k)$$

$i$ 番目が 1 のとき:

$$C(i, j+1, k+1) \leftarrow C(i-1, j, k)$$

$i$ 番目が ? のとき:

$$C(i, j-1, k-1) \leftarrow C(i-1, j, k) \\ C(i, j+1, k+1) \leftarrow C(i-1, j, k)$$

となる. ただし, $k-1 \geq 0$ のときは $k-1$ は $-1$ となり, $j+1 \leq 0$ のときは $j+1$ は $1$ となる.