class Solution {

public:

    bool canJump(vector<int>& nums) {

        int m = 0;

        //每次拓展最右端点，大于nums.size()-1时返回

        for(int i = 0; i < nums.size() ;i++){

            if(i <= m) m = max(m, i + nums[i]);

            if( m >= nums.size() - 1) return true;

        }

        return false;

    }

};

class Solution {

public:

    int jump(vector<int>& nums) {

        if(nums.size() == 1) return 0;

        int m = 0;

        int cnt = 0;

        int i = 0;

        //在一的基础上增加计数，每次到达上一次的最右端点时加一

        while( i < nums.size()){

            int newm = 0;

            while(i <= m){

                newm = max(i + nums[i], newm);

                i++;

            }

            m = newm;

            cnt++;

            if(m >= nums.size() - 1) return cnt;

        }

        return -1;

    }

};

class Solution {

public:

    vector<int> vis;

    bool canReach(vector<int>& arr, int start) {

        vis.resize(arr.size(),0);

        return dfs(arr,start);

    }

    bool dfs(vector<int>& arr, int start){

        if(start < 0 || start >= arr.size() || vis[start]) return false;

        if(arr[start] == 0) return true;

        vis[start] = 1;

        return dfs(arr, start + arr[start]) || dfs(arr,start - arr[start]);

    }

};

class Solution {

public:

    int minJumps(vector<int>& arr) {

        int n = arr.size();

        if(n == 1) return 0;

        vector<int> vis(n,0);//用来记录是否访问过

        int depth = 0;

        //用hash表来记录相同的值

        unordered_map<int,vector<int>> mp;

        for(int i = 0; i < n; i++) mp[arr[i]].push_back(i);

        queue<int> q;

        q.push(0);vis[0] = 1;

        while(q.size()){

            int len = q.size();

            while(len--){

                int t = q.front(); q.pop();

                if(t == n-1) return depth;

                //右跳

                if(t + 1 < n && !vis[t+1]) q.push(t+1),vis[t+1] = 1;

                //左跳

                if(t - 1 >= 0 && !vis[t-1]) q.push(t-1),vis[t-1] = 1;

                //相同的值

                if(mp.count(arr[t])){

                    for(int x:mp[arr[t]]){

                    if(x != t){

                        q.push(x);vis[x] = 1;

                    }

                     }

                    mp.erase(arr[t]);

                }

            }

            depth++;

        }

        return -1;

    }

};

class Solution {

public:

    vector<int> dp;

    int maxJumps(vector<int>& arr, int d) {

        int ans = 0;

        dp.resize(arr.size(),-1);

        for(int i = 0; i < arr.size(); i++)

            ans = max(ans, dfs(arr,i,d));

        return ans;

    }

    //dfs记忆化

    int dfs(vector<int>& arr, int start,int& d){

        //递归出口

        if(dp[start] != -1) return dp[start];

        int res = 1;

        //向左跳

        for(int i = start - 1;i >= 0 && i >= start - d; i--){

            if(arr[i] < arr[start])

            res = max(res,dfs(arr,i,d) + 1);

            else break;

        }

        //向右跳

        for(int i = start + 1; i < arr.size() && i <= start + d; i++){

            if(arr[i] < arr[start])

            res = max(res,dfs(arr,i,d) + 1);

            else break;

        }

        //记忆

        dp[start] = res;

        return res;

    }

};