Show problems as
Classic problem #746EasyArrayDynamic Programming

Min Cost Climbing Stairs

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

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

A maintenance crew has to get up and over a service ladder whose rungs each need patching before they will take weight. The array fees holds the patching charge for every rung, counted from the bottom, so fees[i] is billed the moment a climber rests on rung i.

A climber opens the ascent by resting on rung 0 or on rung 1, whichever they prefer, and is billed for that rung. From whatever rung they are on, the next move lifts them one rung or two rungs higher. The ascent is over as soon as a move carries the climber past the highest rung, and clearing the ladder is not billed.

Return the smallest total charge for an ascent that gets past the top.

Examples

Example 1

Input
fees = [9, 1, 1]
Output
1

The climber opens on rung 1 and is billed 1, then a two-rung move carries them past rung 2, which is the top of this ladder. Nothing more is billed.

Example 2

Input
fees = [1, 2, 3, 100, 1]
Output
5

Resting on rungs 0, 2 and 4 is billed 1 + 3 + 1 = 5, and one more move from rung 4 clears the ladder.

Example 3

Input
fees = [4, 3, 2, 6]
Output
5

Resting on rung 1 and then rung 2 is billed 3 + 2 = 5, and a two-rung move from rung 2 carries the climber past rung 3.

Constraints

  • 2 <= fees.length <= 1000
  • 0 <= fees[i] <= 999

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 cheapest_rung_climb(fees: list[int]) -> int:
Java
public int cheapestRungClimb(int[] fees)

More on the same topics