Frog Jump - Leetcode Solution

The Frog Jump problem is a typical dynamic programming problem that requires a bit of thinking to solve. The problem statement is as follows:

A frog is crossing a river. The river is divided into x units and at ith unit there may or may not exist a stone. The frog can jump from one unit to the next if there is a stone at the next unit. The frog can also jump in the forward direction, but only if there is a stone at a unit exactly j units forward. If the frog can reach the last unit, return true. Otherwise, return false.

Let's break down the problem into smaller pieces.

Step 1: Identify the subproblem

The problem requires us to determine whether the frog can reach the last unit of the river or not. To do that, we will need to take into consideration each unit of the river, and for each unit determine if the frog can reach it or not.

Step 2: Define the state

We will define the state of the problem as follows:

State: dp[i][j] = true/false representing whether the frog can reach the ith unit of the river by jumping j units ahead.

Step 3: Determine the base case

We can determine the base case as follows:

Base case: dp[0][0] = true since the frog starts from the first unit of the river and it can reach itself without jumping.

Step 4: Define the recurrence relation

We can define the recurrence relation as follows:

dp[i][j] = dp[k][j-1] || dp[k][j] || dp[k][j+1] where k is any index from 0 to i-1 such that there is a stone at the kth unit and i-j <= k <= i-1.

Intuitively, this formula represents the fact that the frog can reach the ith unit of the river by jumping j units ahead if it can reach any of the previous units in the range [i-j, i-1] by jumping j-1, j or j+1 units ahead respectively.

Step 5: Return the final result

Finally, we need to return the result of dp[n-1][j] where n is the number of units in the river and j is any valid jump distance.

With this approach, we can solve the Frog Jump problem in O(n^2) time complexity and O(n^2) space complexity. Below is the Python code for the solution:

def canCross(stones):
    n = len(stones)
    dp = [[False for _ in range(n)] for _ in range(n)]
    dp[0][0] = True
    
    for i in range(1, n):
        for j in range(i):
            k = stones[i] - stones[j]
            if k <= j+1:
                dp[i][k] = dp[j][k-1] or dp[j][k] or dp[j][k+1]
                if i == n-1 and dp[i][k]:
                    return True
                
    return False

In this solution, we are iterating over each unit of the river and for each unit we are examining the possible previous units that can lead to that unit. We are storing the result of each subproblem in the dp matrix and returning the final result when we reach the last unit of the river.

1