企业官网建设流程全解析

LeetCode 403这道“青蛙过河”，最近又因为很多人在准备Java面试被翻了出来，标题里那句public boolean canCross(int[] stones)我在编辑器里敲过不下五遍。这题从表面看只是一道判断能否到达终点的题，但真正动手做会发现，它把DFS超时、备忘录设计、动态规划状态定义这些经典考点全串起来了。更绝的是，这道题的坑还不止算法本身——Java写法的细节、边界条件的取舍、甚至你用什么工具辅助理解，都会直接影响能不能一遍AC。

我刷这题一共经历了三个阶段：第一次纯暴力DFS超时，第二次用记忆化搜索勉强通过，第三次借助AI工具把状态转移彻底想明白之后，才发现前面两次都只是“代码对了，脑子没对”。这篇就把我踩过的坑、验证过的思路、还有怎么用现在流行的AI工具把这类Hard题真正吃透，一次讲清楚。适合正在刷LeetCode的Java工程师、准备大厂面试的同学，也适合那些刷题总靠背题解、换个马甲就不会了的人。

1. 先别急着写代码：把题目条件和边界抠清楚

1.1 题目的规则比表面看起来复杂

先看题面：石头的位置是一个严格递增的数组stones，青蛙从第0块石头出发，位置是0。第一跳被强制规定为1个单位，之后每一跳的距离必须落在上一跳距离的[k-1, k, k+1]这个区间里。注意，这里有个特别容易忽略的点：所谓“上一跳距离k”，不是当前在第几块石头，也不是当前位置的下标，而是青蛙上一步真正跳了多远。

举个官方的例子你就懂了。stones = [0,1,3,5,6,8,12,17]，可以这样走：先跳1到位置1（k=1），再从1跳2到位置3（k=2），从3跳2到位置5（k=2），从5跳3到位置8（k=3），从8跳4到位置12（k=4），最后从12跳5到17（k=5），每一步的距离都落在上一跳的±1范围内，所以返回true。

而stones = [0,1,2,3,4,8,9,11]就是经典的false例子。看起来石头很密集，但问题出在4和8之间隔了4，青蛙走到位置4的时候，上一跳最多也就是2（因为它是从1跳到3再跳到4的，中间步长最多2），下一步最多跳3，够不到8，直接卡死。

理解到这个层面，你才会明白为什么这道题不能简单用“当前位置+是否可达”来做状态——同一块石头，以不同的上一跳距离到达，后续的走法范围完全不同。举个例子，同样是到达位置8，如果上一跳是3，那下一跳只能选2、3、4；如果上一跳是5，那下一跳能选4、5、6。所以状态必须把“上一跳距离”也带上，这是整道题的核心。

1.2 容易被忽略的边界条件炸弹

第一块石头一定是0，这是确定的。第二块石头如果不是1，直接返回false，因为第一步强制跳1。这个判断很多人会在代码里漏掉，导致某些用例输出错误。

还有一个数学上的隐藏性质值得单独说。假设青蛙经过了 i 次跳跃到达第 i 块石头（这里的 i 是数组下标），那它当前的上一跳距离 k 最大不会超过 i。道理很简单：第一步最大就是1，之后每一步最多在上一步基础上加1，所以第三步最大是3，第四步最大是4，以此类推。这个性质直接决定了后面备忘录的数组维度怎么设计，也是若干剪枝方案的数学根基。

最后一个边界问题是 n=1 的情况。如果stones长度只有1，也就是只有一块石头在位置0，那青蛙已经在终点了，直接返回true。别觉得这种用例不可能出现，LeetCode的测试数据里什么都有，代码里第一行就该防御住。

2. 从暴力DFS到记忆化搜索：先把思路跑通再谈优化

2.1 为什么纯暴力DFS一定超时

很多人第一反应是DFS硬搜：从当前石头出发，枚举k-1、k、k+1三种跳法，能跳就继续往下递归。逻辑上完全正确，但想一下复杂度就明白了。每一步最多三个分支，路径最深可能到2000层（题目限制石头数量最多2000），理论上最坏是3的2000次方，这个量级比宇宙原子数量还离谱。就算实际数据没有这么极端，LeetCode的判题器也会让你的代码在超时边缘疯狂试探。

关键问题在于，这个递归树里有大量重复子问题。你可能从位置1跳2到达位置3，也可能从位置0跳1到位置1再跳2到位置3，后面的搜索路径完全一样。如果不做缓存，同样的(位置, 上一跳距离)组合会被反复计算，这也是纯DFS过不了的本质原因。

2.2 记忆化搜索的Java实现要点

记忆化搜索就是在DFS外面套一层缓存，把已经算过的状态存下来。这里有个非常关键的Java实现细节：状态是(当前石头下标, 当前上一跳距离k)，所以需要一个二维备忘录。我用的数据结构是Boolean[n][n]，第一维是石头下标，第二维是上一跳距离。

第二维为什么敢开成n而不是某个很大的值？这就是前面提到的数学性质在起作用——能到达第 i 块石头的状态里，上一跳距离 k 最大是 i，而 i 最大是 n-1，所以Boolean[n][n]必然够用，不会越界。

还有一个容易踩的坑：为什么用Boolean[][]而不是boolean[][]？因为boolean数组初始值是false，而false本身是“不可达”的有效答案。如果你用boolean[][]，就没办法区分“这个状态还没算过”和“这个状态算过结果是false”，于是每次都得重算，备忘录形同虚设，照样超时。Boolean包装类的 null 正好用来表示第三种状态“还没算过”，这就是典型的用包装类型换三态逻辑。

代码长这样：

class Solution { private Map<Integer, Integer> posToIndex; private int[] stones; private Boolean[][] memo; public boolean canCross(int[] stones) { this.stones = stones; int n = stones.length; if (n == 1) return true; if (stones[1] != 1) return false; posToIndex = new HashMap<>(); for (int i = 0; i < n; i++) { posToIndex.put(stones[i], i); } memo = new Boolean[n][n]; return dfs(0, 0); } private boolean dfs(int index, int k) { if (index == stones.length - 1) return true; if (memo[index][k] != null) return memo[index][k]; for (int jump = k - 1; jump <= k + 1; jump++) { if (jump <= 0) continue; int nextPos = stones[index] + jump; if (posToIndex.containsKey(nextPos)) { if (dfs(posToIndex.get(nextPos), jump)) { memo[index][k] = true; return true; } } } memo[index][k] = false; return false; } }

这里给每个石头位置建了一个HashMap<Integer, Integer>映射，作用是 O(1) 判断某个位置有没有石头、以及它的下标是多少。千万不要在递归里用线性扫描找下一块石头，虽然n最大2000看着不多，但递归层数一深，线性查找的消耗会被放大很多倍。

2.3 面试官视角：记忆化搜索为什么经常比纯DP更讨喜

我面过不少人，也被人面过。这道题如果用记忆化搜索写，面试官通常会让你继续说说“能不能改成DP”。但记忆化搜索本身有一个真实优势：它天然只计算从起点可达的状态，而且是按需计算。相比之下，很多人的DP写法是从头到尾把所有石头、所有可能的跳数都遍历一遍，即使某些状态根本不会被用到也照样算。

所以你完全可以对面试官说：记忆化搜索本质是递归版的动态规划，是用系统栈换显式循环，好处是代码更贴近“从某块石头出发能不能到终点”的自然思维，坏处是递归有栈深度风险。但在这个题里递归深度最多2000层，Java默认栈没问题，所以你可以放心写。

3. 更标准的动态规划解法：Map加Set的状态转移

3.1 状态定义是关键：map里存的不是布尔值，而是跳数集合

动态规划解法的思路是正向遍历每块石头，维护“每个位置可能以哪些跳数到达”。用Map<Integer, Set<Integer>>，key是石头位置，value是集合，集合里存的是“所有能到达这个位置的上一跳距离”。

这里必须想明白一件事：为什么要存跳数集合而不是直接存一个boolean可达标记？因为决定后续跳跃范围的是上一跳距离 k，不是“到达过没有”。同一个位置，可能经过不同的跳数到达，每一种都会带来不同的下一步选择。举个例子，位置3既可以以跳数1到达，也可以以跳数2到达，前者对应下一步只能跳1或2，后者对应下一步能跳2或3，后续路径完全不同。所以必须把每一种跳数都记录下来。

状态转移方程也很直白：假设当前在处理位置pos，集合里有一个跳数k，那么下一步尝试跳k-1、k、k+1，得到新位置next = pos + jump，如果next在石头集合里，就把jump加进next位置的跳数集合。最终判断终点位置的集合是否为空。

用[0,1,3,5]手动推一遍：

3.2 Java完整实现与细节

public boolean canCross(int[] stones) { int n = stones.length; if (n == 1) return true; if (stones[1] != 1) return false; Map<Integer, Set<Integer>> map = new HashMap<>(); for (int s : stones) { map.put(s, new HashSet<>()); } map.get(0).add(0); for (int i = 0; i < n; i++) { int pos = stones[i]; for (int k : map.get(pos)) { for (int jump = k - 1; jump <= k + 1; jump++) { if (jump <= 0) continue; int next = pos + jump; if (map.containsKey(next)) { map.get(next).add(jump); } } } } return !map.get(stones[n - 1]).isEmpty(); }

注意几个细节。第一，内层循环里jump <= 0必须跳过，因为跳数为负或0没有任何实际意义。第二，遍历map.get(pos)的Set时，如果在循环中往同一个Set里加元素会抛并发修改异常，但这里加的是别的key对应的Set，所以安全。第三，外层循环从第0块石头开始往后推，而map.get(0)初始只包含跳数0，这一步天然保证了第一跳只能是1。

复杂度上，外层循环n块石头，每个石头的跳数集合大小理论上也是O(n)，内层最多尝试3种跳法，所以总时间复杂度O(n^2)，空间复杂度O(n^2)。这个复杂度对n=2000来说完全可接受。

3.3 一个非常实用的剪枝思路

在DP循环里，你可以提前判断“从某块石头出发永远够不到下一块石头”直接终止。依据还是前面那个性质：到达第 i 块石头最多用了 i 次跳跃，所以当前跳数 k 最大不超过 i，下一步能跳的最大距离是i + 1。如果stones[i + 1] - stones[i] > i + 1，说明下一块石头在当前可能的最大跳跃距离之外，后面的石头就更不可能到了，直接返回false。

这个剪枝在石头间距稀疏的用例里特别有效，有时候能把O(n^2)的无效计算直接砍掉大半。而且它逻辑上非常严密，放在DP循环开头一点风险都没有。

4. 实战踩坑记录：这些细节决定AC还是TLE

4.1 备忘录维度设计翻车现场

我第一次写记忆化搜索的时候，第二维直接开了个大常数数组，比如Boolean[2000][10000]，想着“反正距离再大也到不了10000”。结果内存直接炸。后来想明白k <= i这个性质，才敢开Boolean[n][n]。

同一天我还犯过一个更隐蔽的错误：我把memo的第二个下标写成了跳数k，但在递归传参时传成了nextIndex。这个错误在数据量小的时候根本看不出来，直到我手动模拟一个长用例才发现状态被污染了。所以提醒所有写递归的人：memo的下标必须和递归参数一一对应，别图省事拿位置下标去查缓存。

4.2 测试用例与排查建议

平时我刷题习惯准备一套自己的用例，而不是只跑题目给的示例。这道题我固定用这么几组：

• [0,1]：最简可达，返回true
• [0,2]：第一步跳必为1，返回false
• [0,1,3,5]：小规模可达，验证状态转移正确性
• [0,1,2,3,4,8,9,11]：经典false用例
• [0,1,3,5,6,8,12,17]：官方示例true用例
• [0,1,2,3,4,5,100]：后半段巨大间隔，验证剪枝逻辑

如果你跑出来结果不对，优先打印每个位置最后积累的跳数集合，看它和你手推的差在哪。我调试这类题的习惯是：在map更新处加一行临时输出，格式化成表格，一眼就能看出是哪一步转移出了问题。

4.3 有关性能的最后一公里

如果你追求极致，官方题解还有一种把状态压缩到数组的写法：boolean[n][n]，第二维同样表示跳数k。但注意，用数组必须配合前面说的k <= i性质，否则可能越界。我自己更推荐Map写法，可读性好、不容易出越界问题，应对面试完全够用。

还有一个小优化值得提：posToIndex映射里用HashMap是因为Java自带实现足够快，如果你非要秀操作可以用Arrays.binarySearch在递归里二分查找石头位置。但实测下来HashMap的常数更小，代码也更直白，没必要自己给自己加复杂度。

5. 我是怎么用AI辅助把这题彻底吃透的

5.1 让AI当陪练，而不是代写

标题里出现了元宝里的DeepSeek模型，其实这也是我最近刷题工作流里很依赖的一环。但我要先说一个真实体会：让AI直接甩给你完整代码，收获相当有限，因为它给你的是结果，不是思路。我现在的做法是，自己也写一版，然后把以下这段话发给AI：

“请用批评者视角审查以下思路：我用DFS加Boolean[n][n]备忘录，状态是石头下标i和上一跳距离k，递归尝试[k-1, k, k+1]，用HashMap判断下一块石头是否存在。请指出状态定义是否有漏洞、备忘录边界是否正确，不要写完整代码。”

这种提问方式的好处是，AI会真的去审视你的逻辑漏洞，而不是给你背一段标准题解。青蛙过河这道题，最难的就是想明白“同一个位置不同跳数到达是不同状态”，而模型恰恰擅长把这类状态定义问题用不同角度解释给你听。有一次我推演状态转移推迷糊了，让AI用“把上一跳距离想象成青蛙的档位，每个档位对应不同加速能力”来类比，一下子就通了。

5.2 AI答案验证的实用闭环

AI给代码，你必须自己验证，不要盲信。我的标准动作是：

1. 把AI给的答案跑一遍题目自带用例
2. 再跑我自己准备的那组边界用例
3. 让AI把时间复杂度、空间复杂度以及为什么Boolean[n][n]不会越界解释一遍
4. 最后自己关掉所有参考，从零手写一遍

这个闭环做完，比光看题解记得牢得多。我试过让同样的模型解释“为什么boolean[][]会导致超时”，它给出的答案里提到了包装类型的三态问题，正好补上了我知识结构里一个模糊的点。

5.3 关于AI辅助刷题的边界认知

最后想给个提醒：AI工具是很好的陪练和讲解员，但它替代不了你手写代码的肌肉记忆，也替代不了你在面试现场画状态转移图的临场能力。用AI查漏补缺可以，用它代写作业骗自己就没意思了。我个人的经验是，把AI当作“24小时在线的导师”，每一步追问都带着自己的思考，才能把一道Hard题转化成自己的东西。

这道题我前前后后刷了三遍，第一遍靠AI给代码抄过去，第二周重做依然卡壳，直到第三次把状态定义和k <= i这个隐藏性质真正想透，才算彻底吃进肚子里。如果你也卡在这道题，我建议你别急着看答案，先把(石头下标, 上一跳距离)这个状态自己在纸上推十个数据点，推完你会有一种豁然开朗的感觉。LeetCode 403这道青蛙过河，说难很难，说简单也简单——就看你有没有迈过“状态定义”那个坎。