n stepping stones, numbered 1 to n, crosses a river. Stepping on stone i costs fees[i - 1] coins; if fees[i - 1] = -1, the stone is under water and cannot be used. The first stone is never under water.
You stand on stone 1 and have already paid for it. From stone i you may jump to stone i + d with 1 ≤ d ≤ max_jump and i + d ≤ n. You need to reach stone n while paying as little as possible in total (the first and last stones included).
Return the stone numbers along the cheapest path in the order you visit them. If several paths are equally cheap, return the lexicographically smallest one: lists are compared at the first position where they differ, and if one is a prefix of the other, the shorter one is smaller. If stone n cannot be reached, return an empty list.fees=[2, 5, 1, 3, 1, 4], max_jump=2 → [1, 3, 5, 6]
Stones 1 → 3 → 5 → 6 cost 2 + 1 + 1 + 4 = 8, and nothing is cheaper.
fees=[1, 0, 0, 1], max_jump=3 → [1, 2, 3, 4]
The paths 1 → 4, 1 → 2 → 4 and 1 → 2 → 3 → 4 all cost 2. Comparing second elements, the last two have 2 and the first has 4; then [1, 2, 3, 4] beats [1, 2, 4] on the third element.
fees=[3, -1, -1, 2], max_jump=2 → []
From the first stone you can only jump to stones 2 and 3, and both are under water.
fees=[2, 5, 1, 3, 1, 4], max_jump=2
[1, 3, 5, 6]
Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.