A child hops up a staircase with n steps. Each hop must cover exactly one of the sizes listed in hops (distinct positive integers). Two climbs are different if their sequence of hop sizes differs. Write climb_ways(n, hops) returning the number of distinct climbs that land exactly on step n.
Examples
Input: n = 5, hops = [1, 3]
Output: 4
Explanation: 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1.
Input: n = 4, hops = [2]
Output: 1
Input: n = 3, hops = [2]
Output: 0
Constraints
0 <= n <= 1000,1 <= len(hops) <= 5,1 <= hops[i] <= 20- Climbing zero steps counts as one (empty) climb.
- A memoised recursion needs at most
n + 1stack levels.
Goals
- Count ordered sequences by branching over every allowed first move
- Return 0 for impossible states and 1 for the finished state
- Memoise on the remaining height