[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}
\]

となります。

コード

提出したコード

動的計画法

  ll dp[N + 2]{};
  dp[0] = 1;
  for (int i = 0; i < M; i++) {
    cin >> a[i];
    dp[a[i]] = -1;
  }
  for (int i = 0; i < N; i++) {
    if (dp[i] == -1) continue;
    if (dp[i + 1] != -1) {
      dp[i + 1] += dp[i];
      dp[i + 1] %= mod;
    }
    if (dp[i + 2] != -1) {
      dp[i + 2] += dp[i];
      dp[i + 2] %= mod;
    }