AtCoder Beginner Contest 129：C - Typical Stairs

問題

atcoder.jp

解法

dp(i) := i 段目まで登る通り数

として DP を考える．通り数は i が「壊れている床」のとき 0 通り，そうでないときは dp(i - 1) + dp(i - 2) 通りとなる．O(N)．

解答

atcoder.jp