ABC129 C - Typical Stairs - ツバサの備忘録

解法

$i$ 段目の階段にたどり着くには、 $i-1$ 段目もしくは $i-2$ 段目から移動する2つの方法のどちらかを利用する必要があります。
つまり、 $i-1$ 段目に行く移動の種類数と、 $i-2$ 段目に行く移動の種類数がわかれば、 $i$ 段目に行く移動の種類数はその総和で表すことができます。
ということで、

$dp[i] = i$ 段目の階段へ行くような移動方法の種類数

とすると、

$dp[i] = dp[i-1] + dp[i-2]$

となります。
ただし、 $i$ が $a_{j}$ のいずれかであったときは、 $dp[i] = 0$ となります。
また、初期状態では、0段目に必ず居るので、 $dp[0] = 1$ となります。
基本的にはこれでいいのですが、上のような集めるDPだと、 $i=1$ の際のみREをしないように別処理をしなければならないため、自分は配るDPにしました。
$dp[i]$ が影響を与えるのは、 $dp[i+1],dp[i+2]$ なので、 $i+1,i+2$ が $a_{j}$ に含まれなかった場合に、その場所に対して $dp[i]$ を足してあげます。
こちらの場合は、DP配列を多めに確保してあげることによって、特別な処理をする必要がなくなります。
ということでこのDPをしてあげることで、答えが $dp[n]$ に格納されます。