青蛙过河 图解题解

青蛙过河这道题到底在判什么

给一排升序的石子位置 stones，青蛙从第一块出发，第一跳必须是 1 个单位。之后若上一跳跨了 k，这一跳只能跨 k−1、k 或 k+1（步长为正），且每跳都要正好落在石子上，问能不能跳到最后一块。以 stones=[0,1,3,5,6,8,12,17] 为例存在一条可达路径，答案 true。

为什么把所有跳法枚举一遍会炸

每落到一块石子，下一跳在 k−1、k、k+1 三个步长里分岔，一路乘下去是 3 的石子数次方级的路径，石子一多就枚举不完。慢还慢在同一种局面被反复重算：站在石子 6、上一跳步长同为 3，往后那截路是定死的，暴力递归每碰一次却从头再跳。把这类局面结果记下复用，指数级枚举才压得平。

站在同一块石子，为什么还得记住上一跳跳多远

只知道青蛙站在石子 6 不够——它能跳多远得看上一跳跨了几格：上一跳是 1，这跳只能是 1、2；上一跳是 3，这跳能是 2、3、4。同一块石子用不同步长跳上来，往后能走的路就不一样，所以完整的局面必须是『石子位置 + 上一跳步长』这一对。

定成这一对，就满足无后效性（未来只由这对状态决定）：知道『站在 6、上一跳步长 3』，能不能过河就定死了。于是用哈希表（按键直接查值的表）jumps 记账，键是石子位置 x，值是能落到 x 时上一跳的所有可能步长。

每块石子的步长集合怎么往后推

起手把 jumps[0] 设成 {0}：从 0 枚举 0−1、0、0+1 只有 0+1=1 为正，逼出唯一合法的首跳步长 1。之后从左到右扫每块石子 x，取出 jumps[x] 里每个步长 k，试 nk=k−1、k、k+1：只要 nk 为正、落点 x+nk 是石子，就把 nk 记进 jumps[x+nk]。落点是终点就返回能过河，扫完没到就是过不去。

拿题面示例把步长集合一块块填出来

拿题面的 stones=[0,1,3,5,6,8,12,17] 走一遍，先 jumps[0]={0}。从 0 步长 1 到 1、1 步长 2 到 3（站在石子 1、上一跳步长 1，所以这跳能取 k+1=2）、3 步长 2 与 3 到 5 和 6、5 步长 1 到 6，jumps[6] 集齐 {3,1}（3 来自石子 3 步长 3、1 来自石子 5 步长 1）。再往前推，石子 5 步长 3 到 8、石子 6 步长 2 到 8，jumps[8] 凑成 {3,2}；8 步长 4 到 12、12 步长 5 到终点 17，返回 true。路径 0→1→3→5→8→12→17。

青蛙从石子 4 死活跳不到 8，这串为什么只能判 false

换 stones=[0,1,2,3,4,8,9,11]：青蛙能蹭到石子 4，可此时步长最多才 2、这跳最远跨 3，隔着 4 格的石子 8 够不着，jumps[8] 始终空着，返回 last==0 即过不去。每块石子步长集合 O(n) 个、各试 3 向，时间空间都 O(n²)。最易写错处：jumps[0] 忘塞 0，首跳无从触发；漏掉 nk 为正，青蛙往回跳；[0,1] 直达算 true，而 [0,2] 落不到 2 判 false。

Python

from typing import List
from collections import defaultdict
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        stone_set = set(stones)
        jumps = defaultdict(set)
        jumps[0].add(0)
        last = stones[-1]
        for x in stones:
            for k in list(jumps[x]):
                for nk in (k - 1, k, k + 1):
                    if nk > 0 and x + nk in stone_set:
                        if x + nk == last:
                            return True
                        jumps[x + nk].add(nk)
        return last == 0

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_set<int> pos(stones.begin(), stones.end());
        unordered_map<int, unordered_set<int>> jumps;
        jumps[0].insert(0);
        int last = stones.back();
        for (int x : stones) {
            auto cur = jumps[x];
            for (int k : cur) for (int nk : {k - 1, k, k + 1}) if (nk > 0 && pos.count(x + nk)) {
                if (x + nk == last) return true;
                jumps[x + nk].insert(nk);
            }
        }
        return false;
    }
};

Java

import java.util.*;
class Solution {
    public boolean canCross(int[] stones) {
        Set<Integer> pos = new HashSet<>();
        for (int x : stones) pos.add(x);
        Map<Integer, Set<Integer>> jumps = new HashMap<>();
        jumps.computeIfAbsent(0, k -> new HashSet<>()).add(0);
        int last = stones[stones.length - 1];
        for (int x : stones) {
            for (int k : new HashSet<>(jumps.getOrDefault(x, Collections.emptySet()))) {
                for (int nk = k - 1; nk <= k + 1; nk++) if (nk > 0 && pos.contains(x + nk)) {
                    if (x + nk == last) return true;
                    jumps.computeIfAbsent(x + nk, t -> new HashSet<>()).add(nk);
                }
            }
        }
        return false;
    }
}