A skyline artist draws mountain ridges with exactly n up-strokes and n down-strokes. A ridge starts at ground level, never dips below ground, and ends back at ground level. Write ridge_count(n) returning how many distinct ridges can be drawn.
Examples
Input: n = 3
Output: 5
Explanation: writing U for up and D for down, the ridges are UDUDUD, UDUUDD,
UUDDUD, UUDUDD and UUUDDD.
Input: n = 0
Output: 1
Explanation: the flat ridge with no strokes.
Constraints
0 <= n <= 60- Results grow quickly; Python integers handle them. A memoised recursion uses at most
n + 1stack levels.
Goals
- Split a count on the position of the first return to ground level
- Sum products of two smaller counts
- Memoise so the exponential recursion becomes quadratic