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.