Problem Description
A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit. If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.
Key Insights
- The frog can only jump to stones that are reachable based on its previous jump.
- The jump distance can vary by -1, 0, or +1 relative to the last jump.
- A depth-first search or dynamic programming approach can be used to explore the possible states of the frog's position and jump distances.
Space and Time Complexity
Time Complexity: O(n^2) - In the worst case, we may need to evaluate all possible jumps for each stone. Space Complexity: O(n) - We may need to store the state of reachable jump distances for each stone.
Solution
To determine if the frog can reach the last stone, we can use a dynamic programming approach. We maintain a dictionary to track the possible jump distances that can land on each stone. Starting from the first stone (position 0), we initialize the possible jumps to 0 (the starting position). For each stone, we explore all possible jump distances that could land on it and update the reachable states for the next stones based on the allowed jump variations (-1, 0, +1).