Frog Jump DP | Dataford Interview Questions

How would you solve the frog jump problem using dynamic programming?

Given a strictly increasing array stones of stone positions, return True if the frog can reach the final stone from position 0. The first jump must be exactly 1; after a jump of length k, the next jump may have length k - 1, k, or k + 1, and every jump must be positive.

Implement def can_cross(stones):. Return False when the frog cannot reach the final stone.

Example: stones = [0, 1, 3, 5, 6, 8, 12, 17] returns True. stones = [0, 1, 2, 3, 4, 8, 9, 11] returns False.

Constraints

1 <= stones.length <= 2000
stones[0] == 0
0 <= stones[i] <= 2^31 - 1
stones is strictly increasing
A jump length must be a positive integer

Function Signature

def can_cross(stones):

Your question is Frog Jump DP. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem