414. Ways to Climb With a Given Step Set
A staircase has n steps. You may climb any number of steps from a given SET
at a time, and different orders count as different ways. Print how many ways
there are to reach the top exactly. Reaching step 0 counts as one way, the empty
climb.
Problem #220 is this with the step set fixed to {1, 2}, where the answer is
Fibonacci. Making the set an input changes nothing structurally and everything
practically, because the recurrence can no longer be written out by hand:
ways[0] = 1
ways[i] = sum of ways[i - s] over every step s in the set with s <= i
The order of the two loops matters and it is the same question as problem 410: with the TOTAL outermost, every step may follow any prefix, so orderings are counted separately, which is what this problem asks for.
Two cases worth checking. If no step reaches a given height, the count there is
0 and the zeros propagate: with steps {2} and n = 5, the answer is 0 because
every reachable height is even. And n = 0 is 1, not 0, which is the base case
the whole table rests on.
Constraints - `0 ≤ n ≤ 50` - `1 ≤ k ≤ 10` - `1 ≤ step ≤ 50` - The steps are distinct. - The answer fits in a signed 64-bit integer.
Input
The first line contains two integers n and k.
The second line contains k space-separated distinct step sizes.
Output
Print how many ordered ways there are to climb exactly n steps.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.