Typical Stairs [AtCoder Beginner Contest 129 C]

https://atcoder.jp/contests/abc129/tasks/abc129_c

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc129/submissions/5860105

組み合わせ問題でmod10^9+7なので、とりあえずDPできないか考える。
dp[i] := i段目にたどり着くまでの移動方法の組み合わせ
これで解くが、壊れているという制約を無視すると、1段か2段で移動するので、
dp[i+1] += dp[i]
dp[i+2] += dp[i]
という感じに計算していけば良さそう。
壊れているという制約だが、配列Aのままだと扱いにくいので、
ng[i] := i段目が壊れているか
という制約になおしておき、ng[i+1],ng[i+2]がfalseであれば、遷移を行うようにする。
これでdp[N]が答え。

int N, M;
int ng[101010];
mint dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a; cin >> a;
		ng[a] = true;
	}

	dp[0] = 1;
	rep(i, 0, N) rep(d, 1, 3) if (!ng[i + d]) dp[i + d] += dp[i];
	cout << dp[N] << endl;
}