题解 | #几步可以从头跳到尾#

思路：

题目的主要信息：

• n长度的数组，每个元素表示从该数下标位置最多可往后跳跃多少个
• 从1开始，无0的情况

方法一：动态规划（可能会超时）
题目要求的是找出从1跳到n最快的路径，即所需步数最短，我们可以想到遍历所有的路径，从中找出步数最短的路径。
具体做法：
我们可以用dp[i]表示第i个元素到最后一个元素所需要的步数(下标从1开始），起点是n-1到n需要步数为1，依次自顶向下计算：对于第i个元素，如果（数组下标从0开始），则可以一步到位；否则我们遍历i之后的元素，找到最小到n的步数，即（j为往后遍历的数量），并使之加1。
（该方法经多次测试，有超时的风险，可能超时，可能不超时）

class Solution {
public:
    int Jump(int n, vector<int>& A) {
        vector<int> dp(n + 1, INT_MAX);//假设从第n个格子到第n个格子所需步数为max
        if(1 + A[0] >= n) //排除一步到位的
            return 1;
        dp[n - 1] = 1;// 第n-1个格子到第n个格子的步数一定为1
        for(int i = n - 2; i > 0; i--){
            if (i + A[i - 1] >= n){ //可以一步到底
                dp[i] = 1;
                continue;
            }
            dp[i] = INT_MAX;
            // 实现递推公式
            for (int j = 1; j <= A[i - 1]; j++) //寻找之后的最小值
               dp[i] = min(dp[i + j], dp[i]);
            dp[i]++;
        }
        return dp[1];
    }
};

复杂度分析：

• 时间复杂度：，最坏两层遍历
• 空间复杂度：，辅助数组dp

方法二：贪心
利用贪心思想，每次更新到最远的格子。
具体做法：
能否到达指定的格子，也即是经过前面某一格子跳跃到该格子或者可跳跃的距离大于该格子的距离。即记录最后一次跳跃的结束位置，如果上次跳跃的结束最大位置等于当前位置，但还没到达指定位置时，需要更新本次结束的最大位置，并且将次数加一。

class Solution {
public:
    int Jump(int n, vector<int>& A) {
        int step = 0;//最大跳跃次数
        int end = 0;//表示跳跃结束位置
        int res = 0;//表示已经跳跃次数
        for(int i = 0; i < n - 1; i++)
        {
            step = max(step, i + A[i]);  
            if(end >= n) 
                break; 
            if(end == i)  //结束点位置等于当前下标，结束一次跳跃
            {
                end = step;
                res++;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历一次
• 空间复杂度：，常数个变量，无额外空间

方法三：贪心+动态规划
动态规划很浪费时间，我们用方法二的贪心思想来优化它。
具体做法：
首先我们定义一个长度为n+1的dp辅助数组，其中dp[i]表示到第i个元素至少需要的步数，为了使到达i个元素的步数最少，首先要确定前一个元素的下标（j）在哪，可以通过贪心的方式找到j的位置（即找最多），然后转移方程为，即从j位置往前再跳一次就到i位置。

class Solution {
public:
    int Jump(int n, vector<int>& A) {
        vector<int> dp(n + 1, 0);
        for(int i = 2, j = 1; i <= n; i++){
            //贪心地找到达第i个元素的前一步所在下标j
            while(j + A[j - 1] < i)
                j++;
            //从j位置跳一步到达i位置
            dp[i] = dp[j] + 1;
        }
        return dp[n];
    }
};

复杂度分析：

• 时间复杂度：，只遍历了一次数组
• 空间复杂度：，辅助数组dp