Frog Jump

Explore how to determine if a frog can cross a river by jumping on stones using dynamic programming techniques. Learn to apply memoization and tabulation to optimize solutions and master this common coding interview pattern.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

A frog is trying to cross a river by jumping on stones placed at various positions along the river. The river is divided into units, and some units contain stones while others do not. The frog can only land on a stone, but it must not jump into the water.

You are given an array, stones, that represents the positions of the stones in ascending order (in units). The frog starts on the first stone, and its first jump must be exactly $1$ unit.

If the frog’s last jump was of length $k$ units, its next jump must be either ...