Qiita で解説が少ない問題だったので触れてみる。
問題はコチラ。
いきなり回答
雑な気もするが一旦、以下のコードを動かしてほしい。
dp.cpp
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
// data input -------------->
int N, M; cin >> N >> M;
int a; set<int> nums;
for (int i = 0; i < M; i++) {
cin >> a; nums.insert(a);
}
// <-------------------------
// COMMENT
// memory the broken stair information with SET.
// you can check whether current stair is broken with O(N).
// this is why i use set.
vector<long long>dp(N + 1, 0); dp[0] = 1;
for (int i = 1; i <= N; i++) {
if (nums.find(i) != nums.end()){ //if current stair is broken, let's skip.
continue;
}
//key point-----------------
if (i-1 >= 0)
dp[i] += dp[i - 1];
if (i-2 >= 0)
dp[i] += dp[i - 2];
dp[i] = dp[i] % 1000000007;
//---------------------------
}
cout << dp[N] ;
while (1) {}
return 0;
}
回答例1 を試す
cout << dp[N] の前に cout で dp を羅列させてみました。
.cpp
//input
6 1
3
// dp
1 1 2 0 2 2 4
/*
STAIR#0
Every one would start from here.
so dp[0] = 1.
STAIR#1
There is only one way to reach STAIR#1.
so dp[1] += dp[0].
STAIR#2
There are two ways to reach STAIR#2.
1 => 2....dp[2] += dp[1] // we often to write it, such as "dp[2] += dp[1]+1".
0 => 2....dp[2] += dp[0] // but it's not good way to caulcurate combination number.
STAIR#3
here is broken. so no need to action.
STAIR#4
there is only one.
3 => 4....dp[4] += dp[2]
STAIR#5
4 => 5....dp[5] += dp[4]
3 => 5.X.. stair 3 is broken
STAIR#6
5 => 6....dp[6] += dp[5]
4 => 6....dp[6] += dp[4]
*/
// answer
4
上記にあるように、前段、前々段の組み合わせを足していけば答えになることが分かる。
※組み合わせだから掛けて行けば良いかと思い、試したがダメだった。
手を動かしてみよう
何でも良い、上記でコメントした内容に沿って
メモしていけば分かる。以下のような適当な図で良い、やってみる。
動作例としてデータが足りないのであれば
回答例 2, 3 を試して、考えてみると良い。
"前段、前々段の和" に気が付くと簡単だが、
そこに行くまでが大変だったりする(笑)