class Solution {
public:
    vector<map<int , int>> vec;

    bool dfs(vector<int>& stones , int last , int i)//判断如果当前位于第i个石头，且上一跳的距离是last时，能否到达最后一个石头
    {
        if(i == vec.size() - 1) return true;

        if(vec[i].count(last))  return vec[i][last];
        for(int k = last - 1 ; k <= last + 1 ; k++)//枚举当前可以选择的距离
        {
            if(k <= 0) continue;//跳跃距离非正数显然不可能
            //寻找是否存在[stones[i]+k-1,sontes[i]+k+1]范围内的石头
            int j = lower_bound(stones.begin() , stones.end() , stones[i] + k) - stones.begin();
            if(j != stones.size() && stones[j] == stones[i] + k && dfs(stones , k , j))  return vec[i][last] = true;
        }
        return vec[i][last] = false;//最后不要忘了记忆化不可以到达的情况
    }

    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vec.resize(n);
        return dfs(stones , 0 , 0);//假定初始时位于第0块石头，上一跳距离是0，那么当前这一跳距离只能为1（减少特判）
    }
};