Show problems as
Classic problem #70EasyMathDynamic ProgrammingMemoization

Climbing Stairs

Real-world version: Rung Ladder Climbs
Tracked in this browser only
Read Climbing Stairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBasic Dynamic Programming · Dynamic Programming, animated step by step

A maintenance robot waits on the ground under a ladder whose rungs are numbered 1 through n, counting upward from the bottom. Each pull of its winch raises the robot by exactly one rung or by exactly two rungs, and it never lowers itself. The job is finished the moment the robot stands on rung n, and it must not overshoot that rung.

Two climbs are counted separately when their lists of pull sizes differ at some position, so a one-rung pull followed by a two-rung pull is a different climb from a two-rung pull followed by a one-rung pull.

Return how many climbs finish on rung n.

Examples

Example 1

Input
n = 1
Output
1

A single one-rung pull is the only way up, since a two-rung pull would carry the robot past the top.

Example 2

Input
n = 5
Output
8

Writing pulls in order: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2 and 2+2+1.

Example 3

Input
n = 7
Output
21

The climbs that end on rung 7 split into those whose last pull was one rung (13 of them, ending from rung 6) and those whose last pull was two rungs (8 of them, ending from rung 5).

Constraints

  • 1 <= n <= 45

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def ladder_climbs(n: int) -> int:
Java
public int ladderClimbs(int n)

More on the same topics