Toll Stairway
Easy1-D Dynamic ProgrammingFree
Problem
A stairway has n steps numbered 0 to n - 1. Standing on step i costs cost[i] coins, paid once each time you stand on it. From any step you may climb one or two steps.
You may start on step 0 or on step 1. The landing at the top, just above step n - 1 (position n), is free. Return the minimum total you must pay to reach the landing.
Example 1
- Input:
- cost = [10, 15, 20]
- Output:
- 15
Start on step 1, pay 15, then climb two steps straight to the landing.
Example 2
- Input:
- cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
- Output:
- 6
Stand on steps 0, 2, 4, 6, 7 and 9, paying 1 each.
Constraints
- 2 ≤ cost.length ≤ 1000
- 0 ≤ cost[i] ≤ 999
Hint
Show the first hint
Instead of thinking about where to go next, ask: what is the cheapest way to arrive at position i?
Walkthrough
How to approach it
01Clarify before coding
- Do I pay for the step I start on? Yes: you pay cost[i] for every step you stand on, the starting one included. What is free is choosing which of the two to start on.
- Is the landing a step with a cost? No, it is position n and costs nothing.
- Are costs non-negative? Yes, 0 to 999.
02Brute force
Recursively try both starts and, from each step, both a 1-step and a 2-step, summing costs and keeping the minimum. Memoising on the step index turns it into O(n).
Cost: Without memo: O(2ⁿ) time, hopeless for n = 1000. With memo: O(n) time and O(n) space for the memo and the call stack.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.