用C++讲讲 青蛙跳（LeetCode 403）的最佳思路
LeetCode 403 青蛙跳石头，本质是一个「记忆化搜索/动态规划」问题，而不是单纯的贪心或二分能直接解决的，原因是每一步跳跃的步长可以比上一步大 1、相等、或小 1，步长既能增大也能减小，状态里既要记录「在哪块石头上」，又要记录「上一步跳了多远」，这两个维度合在一起才能判断青蛙是否有一条合法路径跳到终点。
最佳思路是：为每块石头维护一个集合，记录「所有能跳到这块石头上的合法上一步步长 k」；从第一块石头（步长为 0）出发，依次处理每块石头能到达的下一块石头，把新的步长记录到目标石头的集合里；最后看终点石头的集合是否非空。
用 index 而不是石头的坐标值作为 dp 数组下标会更高效，因为可以避免每次都用坐标去哈希查找：
class Solution {
public:
bool canCross(vector<int>& stones) {
int n = stones.size();
if (n == 1) return true; // 只有一块石头，青蛙已经在终点
unordered_map<int, int> indexOf; // 石头坐标 -> 下标
for (int i = 0; i < n; ++i) indexOf[stones[i]] = i;
vector<unordered_set<int>> dp(n); // dp[i] = 所有能到达第 i 块石头的步长集合
dp[0].insert(0);
for (int i = 0; i < n; ++i) {
for (int k : dp[i]) {
for (int step = k - 1; step <= k + 1; ++step) {
if (step <= 0) continue; // 步长必须为正
int nextPos = stones[i] + step;
auto it = indexOf.find(nextPos);
if (it != indexOf.end() && it->second > i) {
dp[it->second].insert(step);
}
}
}
}
return !dp[n - 1].empty();
}
};
几个设计上的关键点：
用 vector<unordered_set<int>> 而不是单纯的 vector<bool>，是因为「能否到达某块石头」不够，还需要知道「用什么步长到达的」，才能推出下一步可以跳多远，这是这道题和普通可达性 DP 最大的区别。
外层按石头下标从小到大遍历，保证处理第 i 块石头时，所有能到达它的路径都已经被记录进 dp[i] 了（因为坐标递增，能到达 i 的石头下标一定小于 i），这是一种自然的拓扑顺序，不需要额外排序或者用队列做 BFS。
判断 it->second > i 是为了避免往回跳或者跳到自己身上，保证只往坐标更大的石头前进（其实题目坐标严格递增，跳跃步长为正，理论上 nextPos 一定大于 stones[i]，这个判断更多是防御性写法，实际上 indexOf 里查到的下标天然就会大于 i）。
复杂度上，每块石头最多可能有 O(n) 种不同的到达步长（最坏情况下步长范围能到 n 这个量级），所以总的状态数是 O(n^2)，每个状态尝试 3 种跳法，整体时间和空间都是 O(n^2)，在 LeetCode 给定的数据规模（石头数不超过 2000）下是可以接受的。
也可以写成自顶向下的记忆化搜索版本，用 unordered_map<long long, int>（把 i 和 k 编码成一个 key）做 memo，逻辑上和上面等价，但递归写法在 C++ 里有额外的函数调用开销，且要注意递归深度（最坏 O(n) 层），一般推荐用上面这种自底向上迭代的写法，更稳、更快，也不用担心栈溢出。