Loading
Loading
A garden path crosses a pond on a line of stepping stones. A caretaker charges a toll for every stone you land on. You start on the near bank, just before the first stone, and want to reach the far bank, just after the last stone.
Each hop moves you forward by exactly one or two positions. The banks are free. Return the smallest total toll for the crossing.
tolls = [4, 9, 2, 7, 3]stone 0: 4 + min(bank, bank) = 4reached straight from the bankstone 1: 9 + min(4, bank 0) = 9cheapest to hop over stone 0stone 2: 2 + min(9, 4) = 6come from stone 0stone 3: 7 + min(6, 9) = 13come from stone 2stone 4: 3 + min(13, 6) = 9come from stone 2far bank: min(9, 13) = 9leave from stone 4 or stone 39Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n) time · O(1) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Bank, stone 0 (4), stone 2 (2), stone 4 (3), far bank: 9 in tolls.
Example 2
Land only on the two 1s: bank, stone 1, stone 3, far bank.