#161EasyDynamic Programming· Counting Paths in One Dimension

Staircase With Broken Steps

A hiker stands at the bottom of an old stone staircase with `n` steps and wants to reach the top step, numbered `n`. The ground below the first step is step 0. On each move the hiker climbs either one or two steps. Some steps have crumbled and cannot be stood on. The hiker can jump **over** a broken step (a two-step move may start below it and land above it) but can never land on one. Step 0 is always safe, and so is the top step. Count how many different sequences of moves take the hiker from step 0 to step `n`.

Input format

`n`: the number of the top step; `broken`: an array of distinct step numbers between 1 and `n - 1` that cannot be used.

Output format

An integer: the number of distinct ways to reach step `n` (0 if the top cannot be reached). It always fits in a 32-bit signed integer.

Examples

Input: n = 3, broken = []

Output: 3

With no broken steps the sequences are 1+1+1, 1+2 and 2+1: three ways.

Input: n = 5, broken = [3]

Output: 2

Step 3 cannot be used, so every path must pass through step 2 and then step 4: (1+1 or 2) then 2 then 1, which gives 2 ways.

Input: n = 4, broken = [1, 2]

Output: 0

Two consecutive broken steps block both a 1-step and a 2-step move from step 0, so the top is unreachable and the answer is 0.

Constraints

1 <= n <= 45
0 <= broken.length <= n - 1
Every value in `broken` is distinct and satisfies 1 <= broken[i] <= n - 1.

#dynamic-programming
#counting
#arrays