Posted on

Description

Submission

class Solution {
    int dp[1002];
    int d; 

    int dfs(int cur, vector<int>& arr) {
        if(dp[cur] != 0) return dp[cur];
        int ret = 1;

        for(int i = 1; i <= d; ++i) {
            if(cur + i >= arr.size()) break;
            if(arr[cur+i] >= arr[cur]) break;
            ret = max(dfs(cur+i, arr) + 1, ret);
        }

        for(int i = 1; i <= d; ++i) {
            if(cur - i < 0) break;
            if(arr[cur-i] >= arr[cur]) break;
            ret = max(dfs(cur-i, arr) + 1, ret);
        }
        dp[cur] = ret;
        return ret;
    }
public:
    int maxJumps(vector<int>& arr, int d) {
        this->d = d;
        int ret = 0;
        for(int i = 0; i < arr.size(); ++i) {
            dfs(i, arr);
            ret = max(ret, dp[i]);
        }

        return ret;
    }
};

References

  1. https://www.youtube.com/watch?v=Q2flmQeMxpk

Leave a Reply

Your email address will not be published. Required fields are marked *