为了选出新的首领，青蛙部落准备在河边举办一场比赛，部落的首领必须同时具备强健的体魄和灵活的头脑，所以举办方制定了如下的比赛规则：
- 假定河流被等分为若干个单元格，在其中的一些单元格内放有一块石子。
- 石子的位置存在stones中（用石子所在单元格的序号升序表示）。
- 候选人只能从一块石子跳到另一块石子，跳入水中即视为淘汰。
- 开始时，候选人站在第一块石子上，规定第一步只能跳一个单元格的距离，即只能从单元格1跳到单元格2，即
stones[0]为0，stones[1]必须为1。- 为了选出最优秀的候选人，规定如果候选人上一步跳跃了
k个单位，那么它接下来的跳跃距离只能为k-1、k或k+1个单位，而且只准向前跳（终点的方向）。- 胜利的条件就是跳到最后一块石子上（跳不到或者跳过头都视为淘汰）。
举办方为了比赛的公平和多样性，设计了很多不同的赛道stones，每个候选人都会从这些赛道中抽取自己的赛道，所以必须保证每条赛道都是有解的（即肯定有一种满足比赛规则的跳法能胜利），所以举办方请你来帮助验证赛道的有效性。
示例 1：
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：该赛道是有效的，按照如下方案跳跃：跳1个单位到第2块石子, 然后跳2个单位到第3块石子, 接着跳2个单位到第4块石子, 然后跳3个单位到第6块石子, 跳4个单位到第7块石子, 最后，跳5个单位到第8个石子（即最后一块石子）。
示例 2：
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第5和第6个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。
提示：
2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
标签：回溯，记忆化搜索，动态规划
1.记忆化搜索(DFS)
数据结构：set，map/dict
知识点：
Python：
- 用functools里的@lru_cache(None)及其语法糖@cache来实现记忆化搜索
- set和dict的查找复杂度(a in set(b))都为O ( 1 ) \mathcal{O}(1)O(1)，而list查找复杂度为O ( n ) \mathcal{O}(n)O(n)，bisect查找复杂度为O ( l o g ( n ) ) \mathcal{O}(log(n))O(log(n))
class Solution:
def canCross(self, stones: List[int]) -> bool:
#将list转化为set以便于查找元素是否存在于stones
stones_set = set(stones)
# 实现记忆化搜索
# @cache
@functools.lru_cache(None)
def dfs(pos, step):
'''
因为stones是升序的，所以不存在重复元素，
(非降序则是存在重复元素)
判断当前位置的值是否等于stones最后的值
即可得出我们的蛙哥是否能跳到最后一块石头上
'''
if pos == stones[-1]:
return True
# 遍历蛙哥下一步在k的基础上能跳的距离
for d in [-1, 0, 1]:
'''
如果蛙哥下一步能跳到的位置刚好在stones里，
那么就可以继续往下递归
'''
if step + d > 0 and \
pos + step + d in stones_set and \
dfs(pos + step + d, step + d):
return True
return False
return dfs(0, 0)
2. 动态规划
思路：
首先要确定dp中的状态，这里我们将以石子为主体，将青蛙能否通过跳k个单位到该石子作为每个状态，所以dp是个二维数组，第一个维度自然是stones的长度，要确定第二个维度我们需要知道青蛙最多跳几个单位到达当前石子。因为青蛙第一次必然从stones[0]以一个单位跳到stones[1]，然后下一次最多跳1+1=2到stones[2]，以此类推，我们每次都能以最大距离跳到stones中的下一个石子，那么青蛙最多能跳i个单位到stones[i]，所以我们可以确定青蛙在整个过程中的跳跃距离不可能大于stones的长度n。所以dp第二个维度可以也设为n。
然后要推出状态转移方程。以dp[i][k]为例，dp[i][k]代表青蛙从stones[j]跳k个单位到达stones[i]，有三种可能状态变为dp[i][k]，即dp[j][k+1]→ \rightarrow→dp[i][k]，dp[j][k]→ \rightarrow→dp[i][k]，dp[j][k-1]→ \rightarrow→dp[i][k]，所以状态转移方程为:
dp[i][k] = dp[j][k+1] or dp[j][k] or dp[j][k-1]
数据结构：list (Python), vector (C++)
知识点：
- 这里的动态规划和常见的动态规划不同，当前的状态不是固定从前一个或几个状态转移而来，而是要遍历之前所有可能的状态。
class Solution:
def canCross(self, stones: List[int]) -> bool:
n = len(stones)
# dp[i][k]代表青蛙是否能通过跳k个单位到stones[i]
dp = [[False]*n for _ in range(n)]
# 初始条件青蛙已站在第一块石子上
dp[0][0] = True
for i in range(1, n):
for j in range(i-1, -1, -1):
# k为i和i之前石子j的距离
k = stones[i] - stones[j]
# 如果距离大于j+1，青蛙不可能跳得过来
if k > j + 1:
break
# 状态转移方程
dp[i][k] = dp[j][k-1] or dp[j][k] or dp[j][k+1]
# 只要存在一种方式能到达最后一块石子则返回True
if i == n - 1 and dp[i][k]:
return True
return False