Leetcode 403. Frog Jump

Problem Explanation:

We are given a river as an array of stones represented by their positions in ascending order. The problem requires us to determine whether a frog, starting from the first stone, can reach the last stone. Given some rules - the first jump by the frog should be 1 unit and for the subsequent jumps, if the last jump was k units, the next jump can be either k-1, k, or k+1 units, and with the restriction that the frog can't hop more than length of the stones units at once.

Walkthrough of solution:

The main approach of this solution involves Dynamic Programming which allows us to keep track of whether the frog can reach stone 'n' having hopped 'k' units to get there.

We define a dp table with dimensions: number of stones x (number_of_stones+1) because it is guaranteed that the frog can’t jump more than the total number of stones units. Initially, all entries in dp table are set to false, which means it is initially assumed that the frog cannot reach any stone. However, the frog starts at the first stone, so we set dp[0][0] to true.

Now, we start iterating over the stones. For each stone, we check all previous stones which could reach the current stone under the rules. So for each previous stone, we calculate k (stones[i] - stones[j]) and then check whether for the previous stone, jumping x units (with x = k-1, k or k+1) could reach that stone. If yes, then reaching the current stone is possible and we update the dp value accordingly.

Finally, we return any of the last entry in the dp table, if true it means the frog can reach the last stone, if false it means it's not possible.

Let's consider an example below:

e.g. For input stones = [0,1,3,5,7,9,12,16]

The frog starts at first stone (0), which is always true dp[0][0] = true. On the second stone (1), the frog can only hop 1 unit from the first stone, which is true dp[1][1] = true. For the third stone (3), the frog can only hop 2 units from the second stone, dp[2][2] = dp[1][1 || 2 || 3] = true. For the fourth stone (5), the frog can hop 1 unit from the third stone, dp[3][2] = dp[2][1 || 2 ||3] = true. Following this method, we can see that frog can reach the last stone.

Python Solution:

1
2python
3class Solution:
4    def canCross(self, stones) -> bool:
5        if stones[1] != 1:
6            return False
7        d = {x: set() for x in stones}
8        d[1].add(1)
9        for x in stones[:-1]:
10            for j in d[x]:
11                for k in range(j - 1, j + 2):
12                    if k > 0 and x + k in d:
13                        d[x + k].add(k)
14        return bool(d[stones[-1]])

Java Solution:

1
2java
3public class Solution {
4    public boolean canCross(int[] stones) {
5        int n = stones.length;
6        boolean[][] dp = new boolean[n][n + 1];
7        dp[0][1] = true;
8        for (int i = 1; i < n; ++i) {
9            for (int j = 0; j < i; ++j) {
10                int k = stones[i] - stones[j];
11                if (k <= i) {
12                    dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
13                    if (i == n - 1 && dp[i][k]) {
14                        return true;
15                    }
16                }
17            }
18        }
19        return false;
20    }
21}  

Javascript Solution:

1
2javascript
3var canCross = function(stones) {
4    let dp = Array(stones.length).fill(0).map(()=>Array(stones.length).fill(false));
5    dp[0][1] = true;
6    for(let i = 1; i < stones.length; i++){
7        for(let j = 0; j < i; j++){
8            const k = stones[i] - stones[j];
9            if(k <= i){
10                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
11            }
12        }
13    }
14    for(let i = 1; i < stones.length; i++){
15        if(dp[stones.length - 1][i]){
16            return true;
17        }
18    }
19    return false;
20};

C++ Solution:

1
2c++
3class Solution {
4public:
5    bool canCross(vector<int>& stones) {
6        const int n = stones.size();
7        vector<vector<bool>> dp(n, vector<bool>(n + 1));
8        dp[0][0] = true;
9        for (int i = 1; i < n; ++i){
10            for (int j = 0; j < i; ++j) {
11                const int k = stones[i] - stones[j];
12                if (k > n) continue;
13                for (const int x : {k - 1, k, k + 1}){
14                    if (0 <= x && x <= n){
15                        dp[i][k] = dp[i][k] || dp[j][x];
16                    }
17                }
18            }
19        }
20        return any_of(begin(dp.back()), end(dp.back()), [](bool val) { return val; });
21    }
22};

C# Solution:

1
2csharp
3public class Solution {
4    public bool CanCross(int[] stones) {
5        var dp = new bool[stones.Length, stones.Length];
6        dp[0, 0] = true;
7
8        for (var i = 1; i < stones.Length; ++i) {
9            for (var j = 0; j < i; ++j) {
10                var k = stones[i] - stones[j];
11                if (k <= 0 || k > stones.Length || !dp[j, k] && (k <= 1 || !dp[j, k-1]) && !dp[j, k+1]) {
12                    continue;
13                }
14
15                dp[i, k] = true;
16                if (i == stones.Length - 1) {
17                    return true;
18                }
19            }
20        }
21
22        return false;
23    }
24}

All of those solutions are based on the same approach I've walked through before and handle this problem by using Dynamic programming. In summary, our objective was to understand an algorithm that identifies whether a given frog can possibly reach the end of the path subject to certain conditions. Different programming languages including python, Java, JavaScript, C++, and C# were used to provide a full-scale solution which is achieved by applying the concept of Dynamic Programming.

The subject problem is a typical dynamic programming problem that can be solved with efficient time complexity. For each stone, instead of looking forward to determine the next jump, we should look backward to check if the previous stone can reach the current stone under the defined conditions.

Lastly, the issue at hand becomes much simpler to tackle if approached in the manner of think DP- where we break down the problem into sub-problems and solve for each sub-problem only once. This approach provides an efficient way to find out whether a frog can reach to the end of the river by only examining the stones once.

Always remember, good knowledge of dynamic programming can give you an edge when it comes to solving complex problems, and thus it's key to understand and master dynamic programming problems. Be it Python, Java, JavaScript, or any preferred language- mastering this concept should make you a better programmer altogether!