Frog Jump

A frog is crossing a river. The river is divided into x 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 is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 2³¹.
• The first stone's position is always 0.

At first, I thought it'a a DP problem, but it's not. The confusion comes from the question Jump game. However, since we have the restriction that the frog can jump only k - 1, k or k + 1 stones, whether the frog can jump to current stone has no relation to if frog can jump to next stone. It's possible that the current jump is 4, and next distance is 2, so you cannot jump to that stone.

A better way is to use recursion. From the first stone, we calculate what's the next stone the frog can jump to, if we find one, recursively call the function to calculate the next stone we can jump to, exit when we reach the last stone.

If you simply follow this manner, you will have TLE. So how to optimize. Since we are calculating forwardly, it's possible the same stone and largest jump it has has been calculated before, and which is definitely not working (otherwise we exit the function). We can use a visited set to track all stone and jumps we had, if we already see the combination, we directly return false because we know it's not going to work.

public boolean canCross(int[] stones) {
        int len = stones.length;
        if (len <= 1) {
            return true;
        }
        if (len > 1 && stones[1] != 1) {
            return false;
        }
        Set visited = new HashSet<>();
        return checkCanCross(1, 1, stones, visited);
    }
    
    private boolean checkCanCross(int start, int dist, int[] stones, Set visited) {
        if (start >= stones.length - 1) {
            return true;
        }
        if (dist <= 0 || !visited.add(start + "," + dist)) {
            return false;
        }
        for (int i = start + 1; i < stones.length; i++) {
            int curr = stones[i] - stones[start];
            if (curr > dist + 1) {
                break;
            }
            if (curr == dist - 1 || curr == dist || curr == dist + 1) {
                if (checkCanCross(i, curr, stones, visited)) {
                    return true;
                }
            }
        }
        return false;
    }