Atcoder解いてみた AtCoder Beginner Contest C - Typical Stairs

AtCoder Beginner Contest C - Typical Stairs

問題はこちら

回答

素直に1段上がるか、2段上がるか都度選択するシミュレーションは行えない
階段どうしで連結させてグラフを作れるため、DFS, BFSを考えたが重複して訪問するため、これもなし
段数の状態遷移が発生し、ある状態への到達元が複数あるため、DPを疑い、実装した
詳細は実装へ

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N;
int M;
std::vector<bool> A;

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M;

	A.resize(N+2);
	for (int i = 0; i < M; i++) {
		int a;
		std::cin >> a;
		A[a] = true;
	}

	std::vector<long long> dp(N + 2);

	dp[0] = 1;

	for (int s = 0; s < N; s++) {
		for (int d = 1; d <= 2; d++) {
			int t = s + d;

			if (A[t] == true) {
				continue;
			}

			dp[t] += dp[s];
			dp[t] %= 1000000007;
		}
	}

	std::cout << dp[N] % 1000000007 << std::endl;
	return 0;
}