1344. 跳跃游戏 V


图片说明
图片说明
图片说明


记忆化搜索即可。

class Solution {
public:
    vector<int>g[1024];
    int dp[1003];
    int dep=0;
    void dfs(int u,int pos){
        dep=max(dep,pos);
        if(dp[u]){
            dep=max(dep,pos-1+dp[u]);
            return;
        }
        for(int v:g[u]){
            dfs(v,pos+1);
        }
    }
    int maxJumps(vector<int>& a, int d) {
        int n=a.size();
        pair<int,int>p[n+1];
        for(int i=0;i<n;i++){
            p[i]={a[i],i};
            for(int j=i-1;j>=max(0,i-d);j--){
                if(a[i]>a[j])g[i].push_back(j);
                else break;
            }
            for(int j=i+1;j<=min(n-1,i+d);j++){
                if(a[i]>a[j])g[i].push_back(j);
                else break;
            }
        }
        sort(p,p+n);
        int ans=0;
        for(int i=0;i<n;i++){
            dep=0;
            dfs(p[i].second,1);
            ans=max(ans,dep);
            dp[p[i].second]=dep;
        }
        return ans;
    }
};