## 403. Frog Jump

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:trueExplanation: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:falseExplanation: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[i] == 0`

## Rust Solution

```
struct Solution;
use std::collections::HashMap;
use std::collections::HashSet;
use std::iter::FromIterator;
impl Solution {
fn can_cross(stones: Vec<i32>) -> bool {
let n = stones.len();
let end = stones[n - 1];
let mut memo: HashMap<(i32, i32), bool> = HashMap::new();
let stones: HashSet<i32> = HashSet::from_iter(stones);
Self::dp(0, 1, &mut memo, &stones, end)
}
fn dp(
start: i32,
k: i32,
memo: &mut HashMap<(i32, i32), bool>,
stones: &HashSet<i32>,
end: i32,
) -> bool {
if let Some(&res) = memo.get(&(start, k)) {
return res;
}
let res = if start + k == end {
true
} else {
if stones.contains(&(start + k)) {
if k - 1 > 0 {
Self::dp(start + k, k + 1, memo, stones, end)
|| Self::dp(start + k, k, memo, stones, end)
|| Self::dp(start + k, k - 1, memo, stones, end)
} else {
Self::dp(start + k, k + 1, memo, stones, end)
|| Self::dp(start + k, k, memo, stones, end)
}
} else {
false
}
};
memo.insert((start, k), res);
res
}
}
#[test]
fn test() {
let stones = vec![0, 1, 3, 5, 6, 8, 12, 17];
let res = true;
assert_eq!(Solution::can_cross(stones), res);
let stones = vec![0, 1, 2, 3, 4, 8, 9, 11];
let res = false;
assert_eq!(Solution::can_cross(stones), res);
}
```

Having problems with this solution? Click here to submit an issue on github.