Frog Across the Stones
A frog sits on stone 0 of a row of stones and wants to reach the last stone. From stone i it can jump to stone i + 1 or to stone i + 2. A jump from stone i to stone j costs abs(heights[i] - heights[j]).
Return the smallest total cost of the jumps that take the frog to the last stone. With a single stone the frog is already there, so return 0.
Example 1
heights [10,30,40,20]
returns 30
Jump from stone 0 to stone 1 (cost 20), then from stone 1 to stone 3 (cost 10).
Example 2
heights [30,10,60,10,60,50]
returns 40
Jump 0 to 2 (cost 30), 2 to 4 (cost 0) and 4 to 5 (cost 10).
Constraints
1 <= len(heights) <= 1000 <= heights[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Hop One or ThreeBeginner
- N-th Tribonacci NumberBeginner
- Paving With Colored SlabsBeginner
- Pell NumbersBeginner
- Savings With InterestBeginner
- Stacked CansBeginner
- Sum of the Last kBeginner
- Take One, Two or ThreeBeginner