# LeetCode 403. Frog Jump

## Description

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 < 231.
• The first stone’s position is always 0.
Example 1:
```[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. 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:

```[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.
```

## 描述

• 石子的数量 ≥ 2 且 < 1100；
• 每一个石子的位置序号都是一个非负整数，且其 < 231；
• 第一个石子的位置永远是0。
示例 1:
```[0,1,3,5,6,8,12,17]

```

```[0,1,2,3,4,8,9,11]

```

### 思路

• 动态规划。记走到当前 stone 位置 i 的走法为 steps「type：List」；
• 为了走到下一个位置 j，我们遍历 steps 中的每个 step，于是我们有（step -1，step，step +1 ）三种向前走的走法；
• 我们找到三种走法中能够走到下一个位置 j 的走法，并记录 从上一个位置走到 j 花的步数 step；
• 我们在遍历的过程中判断时候有任意一次走到了结尾位置，如果有返回 True；如果遍历完了都没有，返回 False；
• 以 stones 为键构建字典，键 stone，值为 List，表示从上一个位置到当前位置花费的步数；
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-09-08 08:01:56

from typing import List

class Solution:
def canCross(self, stones: List[int]) -> bool:
stages = {x: set() for x in stones}
stages[0] = {0}
end = stones[-1]

for key in stones:
steps = stages[key]
# 如果 steps 为空，说明不能到达当前位置，可以直接返回 False
if not steps:
return False
# 遍历 steps 中的每一个 step，每一个 step 有三种向前走的走法
# 如果任意一种走法达到了结尾，退出循环，返回 True
if any(map(lambda step: self.__jump(stages, step, key, end), steps)):
return True

return False

def __jump(self, stages, step, start, end):

steps = (step - 1, step, step + 1)
for s in filter(lambda x: x > 0 and start + x in stages, steps):
if start + s == end:
return True

return False
```