力扣例题：跳跃游戏V

给你一个整数数组?arr?和一个整数?d?。每一步你可以从下标?i?跳到：

• i + x?，其中?i + x < arr.length?且?0 < x <= d?。
• i - x?，其中?i - x >= 0?且?0 < x <= d?。

除此以外，你从下标?i?跳到下标?j?需要满足：arr[i] > arr[j]?且?arr[i] > arr[k]?，其中下标?k?是所有?i?到?j?之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你?最多?可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

解题分析：

按题目所说，给定一个数组?和整数d，我们从第i个点可以跳到距离i为d范围内的所有点，当然不包括自身。并且，假设从下标i跳到下标j，arr[i]>arr[j]，且arr[i]要大于i到j中的所有数。值得注意的是，题目是可以从数组中的任意一个地方开始跳跃，那么这道题就可以试着用动态规划的方法来写。我们就用dp[i]来表示从i位置开始，最多可以访问的下标。我们就可以列出动态规划式子：

在距离i点d范围内的最大值。dp[i]=max(dp[i-d]..dp[i-1],dp[i+1],dp[i+d])+1。当然，对于这些arr[i-d]...arr[i+d]中的点计为j，i点到j点中的任何点t，arr[i]>arr[t]。那也就是说，对于任意的i点出发，我们只需要遍历它左边的d个点和右边的d个点，我们就可以得到dp[i]的取值。当然对于这道题我们就不能直接从头开始遍历，我们注意到dp[i]的取值不仅仅与他前面的dp状态值有关，他还和他后面的状态值有关。也就是说，在对dp数组进行状态赋值的时候，我们就需要考虑距离d范围内是否所有都已经赋值完成。为了实现这个步骤，我们在遍历的时候就只需要查看dp[j]是否被遍历过了，如果没有，那就先计算dp[j]，得到dp[j]的值后再来计算dp[i]。我们可以用递归来实现这个操作。

总结：

我们设一个dp数组，初始值赋值为-1。dp[i]用来代表从i点出发最多可以访问的下标。我们从头开始遍历，对于一个点，遍历到当前点对该值赋值为1，表示从该点出发的初始经历下标为1。如果所有满足约束条件（也就是距离d范围内，并且满足i到j内的点都存在arr[i]>arr[j]）的点都已经赋值完成，那么就可以对dp[i]进行赋值，如果不满足，那就先赋值不满足条件的那个点，直到所有不满足条件的点都赋值后，就可以对dp[i]进行赋值。

最后对dp数组赋值完成后dp数组内的最大值那就是我们要求的答案。

代码展示：

class Solution {
public:
    vector<int>dp;
    void dfs(vector<int>& a,int x,int d,int n){
        if(dp[x]!=-1)return ;
        dp[x]=1;
        for(int i=x-1;i>=0&&x-i<=d&&a[x]>a[i];i--){
            dfs(a,i,d,n);
            dp[x]=max(dp[x],dp[i]+1);
        }
        for(int i=x+1;i<n&&i-x<=d&&a[x]>a[i];i++){
            dfs(a,i,d,n);
            dp[x]=max(dp[x],dp[i]+1);
        }
    }
    int maxJumps(vector<int>& arr, int d) {
        int n=arr.size();
        dp.resize(n,-1);
        for(int i=0;i<n;i++)dfs(arr,i,d,n);
        return *max_element(dp.begin(),dp.end());
    }
};

代码解释：

我们用dfs来进行广度优先，将dp数组中的值都赋值为-1来代表刚开始都没有经历下标。对dp数组中每一个点都加入到动态规划赋值中去。对于赋值完成的我们不做更改，对于没有完成的我们就判断符合约束条件内的所有点是否都已经赋值，没有就先将他进行赋值，赋值完成后那就对当前点赋值。最后赋值完成的dp数组内的最大值就是所求解。

复杂度分析：

• 时间复杂度：O(Nd)，其中?N 是数组?arr?的长度。

• 空间复杂度：O(N)。