[AtCoder] ABC 129 C – Typical Stairs

問題

方針

動的計画法

今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。

\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。また、\( i = a_j \ (1 \leq j \leq M)\) を満たす全ての \( i \) について、\( d_i = -1 \) とします。その他の \( i \) については、\( d_i = 0 \) と初期化します。

次に、遷移の仕方は、\( d_i \neq -1 \) を満たし、\( d_{i + 1} \neq -1 \) または、\( d_{i+2} \neq -1\) を満たすとき、それぞれ遷移できるので、

\[
\begin{eqnarray}
d_{i+1} &=& d_{i+1} + dp_{i}\\
d_{i+2} &=& d_{i+2} + dp_{i}
\end{eqnarray}
\]

となります。

コード

提出したコード

動的計画法