A shuttle lift in a mine starts at ground level (floor 0) and makes exactly n moves, each going up one floor or down one floor. It may never go below floor 0 or above floor top, and after the last move it must be back at floor 0. Write lift_trips(n, top) returning the number of different move sequences that satisfy all the rules.
Examples
Input: n = 4, top = 2
Output: 2
Explanation: UDUD and UUDD.
Input: n = 6, top = 2
Output: 4
Explanation: UDUDUD, UDUUDD, UUDDUD, UUDUDD; UUUDDD reaches floor 3 and is illegal.
Constraints
0 <= n <= 200,0 <= top <= 200- Recursion depth is at most
n + 1.
Goals
- Track two state variables: moves left and current height
- Prune moves that break the floor or ceiling constraints
- Memoise on (remaining, height)