# [403. Frog Jump](https://leetcode.com/problems/frog-jump/)
###### tags: `Dynamic Programming`, `Bloomberg`

Description:
A frog is crossing a river. The river is divided into some number of 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 can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be `1` unit.

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

Example 1:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Constraints:

* `2 <= stones.length <= 2000`
* `0 <= stones[i] <= 2^31 - 1`
* `stones[0] == 0`
* stones is sorted in a strictly increasing order.

Solution:
* DP + HashMap

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        // map{i, j}: the frog could jump j units from ith stone
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, new HashSet<>());
        }
        map.get(0).add(1);
        
        for (int i = 1; i < n; i++) {
            Set<Integer> jumpsFromI = map.get(i);
            for (int j = 0; j < i; j++) {
                int dis = stones[i] - stones[j];
                if (map.get(j).contains(dis)) {
                    jumpsFromI.add(dis);
                    jumpsFromI.add(dis + 1);
                    jumpsFromI.add(dis - 1);
                    if (i == n - 1) return true;
                }
            }
        }
        
        return false;
    }
}

* DP

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n + 1];
        // dp[i][j]: whether the frog could jump j units from ith stone
        dp[0][1] = true;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int dis = stones[i] - stones[j];
                /* important */
                // if dis is lessor than zero, continue
                // if dis is larger than i, continue
                // if the frog cannot jump to i from j with dis unit, continue
                if (dis < 0 || dis > i || !dp[j][dis]) continue;
                dp[i][dis] = true;
                if (dis > 0) dp[i][dis - 1] = true;
                if (dis < n) dp[i][dis + 1] = true;
                if (i == n - 1) return true;
            }
        }
        return false;
    }
}