青蛙过河

记住「jumps[x] 记到 x 的步长、每步尝试 k−1/k/k+1、落在石子就记下、碰到终点即 true」,下面逐石子套它。

初始化:jumps[0]={0}。这个「0」是技巧:它让第一跳的步长 nk=0+1=1 恰好满足「首跳为 1」的规则。

处理石子 0(紫):它的步长集合是 {0}。对每个 k,试着往前跳 k−1、k、k+1。

从 0 用步长 1 跳到石子 1(绿)。把步长 1 记进 jumps[1],以后从 1 还能继续往前。

处理石子 1(紫):它的步长集合是 {1}。对每个 k,试着往前跳 k−1、k、k+1。

从 1 用步长 1 会落到 2,但那里没有石子,这一跳不行。

从 1 用步长 2 跳到石子 3(绿)。把步长 2 记进 jumps[3],以后从 3 还能继续往前。

处理石子 3(紫):它的步长集合是 {2}。对每个 k,试着往前跳 k−1、k、k+1。

从 3 用步长 1 会落到 4,但那里没有石子,这一跳不行。

从 3 用步长 2 跳到石子 5(绿)。把步长 2 记进 jumps[5],以后从 5 还能继续往前。

从 3 用步长 3 跳到石子 6(绿)。把步长 3 记进 jumps[6],以后从 6 还能继续往前。

处理石子 5(紫):它的步长集合是 {2}。对每个 k,试着往前跳 k−1、k、k+1。

从 5 用步长 1 跳到石子 6(绿)。把步长 1 记进 jumps[6],以后从 6 还能继续往前。

从 5 用步长 2 会落到 7,但那里没有石子,这一跳不行。

从 5 用步长 3 跳到石子 8(绿)。把步长 3 记进 jumps[8],以后从 8 还能继续往前。

处理石子 6(紫):它的步长集合是 {1, 3}。对每个 k,试着往前跳 k−1、k、k+1。

从 6 用步长 1 会落到 7,但那里没有石子,这一跳不行。

从 6 用步长 2 跳到石子 8(绿)。把步长 2 记进 jumps[8],以后从 8 还能继续往前。

从 6 用步长 2 跳到石子 8(绿)。它的集合里已有 2。

从 6 用步长 3 会落到 9,但那里没有石子,这一跳不行。

从 6 用步长 4 会落到 10,但那里没有石子,这一跳不行。

处理石子 8(紫):它的步长集合是 {2, 3}。对每个 k,试着往前跳 k−1、k、k+1。

从 8 用步长 1 会落到 9,但那里没有石子,这一跳不行。

从 8 用步长 2 会落到 10,但那里没有石子,这一跳不行。

从 8 用步长 3 会落到 11,但那里没有石子,这一跳不行。

从 8 用步长 2 会落到 10,但那里没有石子,这一跳不行。

从 8 用步长 3 会落到 11,但那里没有石子,这一跳不行。

从 8 用步长 4 跳到石子 12(绿)。把步长 4 记进 jumps[12],以后从 12 还能继续往前。

处理石子 12(紫):它的步长集合是 {4}。对每个 k,试着往前跳 k−1、k、k+1。

从 12 用步长 3 会落到 15,但那里没有石子,这一跳不行。

从 12 用步长 4 会落到 16,但那里没有石子,这一跳不行。

从 12 用步长 5 正好跳到终点 17!青蛙过河成功,直接返回 true。

回放一条可行路径:0→1→3→5→8→12→17,每一跳的步长都满足「上一跳 ±1」的规则,最终落在终点 17。答案 true。

边界:[0,1] 直达 true;[0,2] 首跳不够 false;大缺口 false。

两个延伸:可记忆化 DFS(石子,步长)等价;状态必须含步长故非一维。