Next

Ledge climb sequences

Write codeEasy10 min

Your task

In a platformer game, your character climbs a tower of n ledges starting from the ground (ledge 0). Each dash move ascends exactly 1, 2, or 3 ledges. Return the number of distinct sequences of dash moves that land the character exactly on ledge n. If n is 0 the character is already at the top, so return 1. For example, n = 3 has 4 sequences: 1+1+1, 1+2, 2+1, and 3.

Examples

count_dash_routes(n: int) -> int
Example 1
Inputcount_dash_routes(3)
Output4
Example 2
Inputcount_dash_routes(5)
Output13