Frog Jump

JavaView on GFG

Time: O(n^2)

Space: O(n^2)

Intuition

Frog jumps on stones; can jump k-1, k, or k+1 from current position. DP to check if last stone reachable.

Algorithm

1HashMap: stone -> set of valid jump sizes to reach it.
2For each jump k from current stone: if stone+k-1, stone+k, stone+k+1 exist: add to their sets.

Common Pitfalls

•Same as LC 403. Use HashMap<stone, Set<jump>>. Only works if first jump is exactly 1.

Frog Jump.java

Java

// Approach: DP/BFS. State = (stone index, last jump size). A frog can reach stone s from stone s-k, s, s+k.
// Time: O(n^2) Space: O(n^2)
import java.util.*;

class Solution {
    int minCost(int[] height) {
        int n = height.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);

        return memo(height, dp, 0, n);
    }

    private int memo(int[] height, int[] dp, int st, int n) {
        if (dp[st] != -1)
            return dp[st];
        if (st >= n - 2)
            return dp[st] = Math.abs(height[st] - height[n - 1]);

        int one = memo(height, dp, st + 1, n) + Math.abs(height[st] - height[st + 1]);
        int two = memo(height, dp, st + 2, n) + Math.abs(height[st] - height[st + 2]);

        return dp[st] = Math.min(one, two);
    }
}

Was this solution helpful?