## Count Paths Without Three Consecutive Moves A frog starts at `(0, 0)` and must reach `(right_steps, up_steps)`. Every move is exactly one unit right (`R`) or one unit up (`U`). A valid path may never contain `RRR` or `UUU` as a contiguous sequence. Implement: ```text count_paths(right_steps, up_steps) -> integer ``` Return the number of distinct valid move sequences that use exactly `right_steps` right moves and `up_steps` up moves. ### Constraints - `0 <= right_steps <= 20` - `0 <= up_steps <= 20` - The empty path for `(0, 0)` counts as one valid path. - Return the exact count; no modulus is used. - Paths that contain three identical consecutive moves are invalid even if the run occurs at the beginning or end. ### Examples ```text count_paths(1, 1) -> 2 ``` The valid paths are `RU` and `UR`. ```text count_paths(3, 0) -> 0 ``` The only possible sequence is `RRR`, which violates the rule. ```text count_paths(7, 6) -> 285 ``` ### Clarifications - Two paths are different when their move sequences differ. - The frog cannot move left, down, or outside the rectangle determined by the start and destination. - A run of exactly two equal moves is allowed. ### Hints - Position alone does not capture enough information to decide whether the next move is legal. - Consider tracking the previous direction and the length of its current run. - A memoized search or a bottom-up dynamic program avoids enumerating all raw paths. ### Discussion Extensions - How would the state change if at most `k` consecutive moves in one direction were allowed? - What are the time and space complexities in terms of the two step counts? - How could memory be reduced in a bottom-up implementation?