Climbing Stairs with Broken Steps (Memoization)

Problem

You stand on step 0 of a staircase and want to reach step n exactly. In one move you may climb 1, 2, …, k steps. Some steps are broken: you may never land on them.

Read n and k (0 ≤ n ≤ 90, 1 ≤ k ≤ 10), then m, then m distinct broken step numbers (each between 1 and n). Print the number of different move sequences as Ways: X. The answer is guaranteed to fit in a long.

Write a recursive method ways(s) = number of ways to reach n from step s, and memoize it (a long[] plus a boolean[] "already computed" array, or a HashMap<Integer, Long>). Without memoization the largest tests will not finish.

Input:

6 2
1
3

Output:

Ways: 4

Notes: for n = 0 there is exactly one way (do nothing). If step n itself is broken, the answer is 0. When m is 0 the third line is empty or missing.

Your solution

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.

← D1.1 Subsets with a Target Sum D2.1 Generic Minimum and Maximum with Pair<A, B> →