本题数据范围只有 ，所以 勉强能过。

如果面试官要将数据范围出到 ，又该如何求解呢？

我们需要考虑 的做法。

其实通过 这个数据范围，就已经可以大概猜到是道 DP 题。

我们定义 为到达第 个位置所需要的最少步数，那么答案是 。

学习过 路径 DP 专题 的同学应该知道，通常确定 DP 的「状态定义」有两种方法。

• 一种是根据经验猜一个状态定义，会结合题目给定的维度，和要求的答案去猜。

• 另外一种则是通过设计一个合理的 DFS 方法签名来确定状态定义。

这里我是采用第一种方法。

至于如何确定「状态定义」是否可靠，关键是看使用这个状态定义能否推导出合理的「状态转移方程」，来覆盖我们所有的状态。

不失一般性的考虑 该如何转移：

我们知道最后一个点前面可能会有很多个点能够一步到达最后一个点。

也就是有 。

然后我们再来考虑集合 有何特性。

不然发现其实必然有 。

推而广之，不止是经过一步能够到达最后一个点的集合，其实任意连续的区间都有这个性质。

举个????，比如我经过至少 5 步到达第 个点，那么必然不可能出现使用步数少于 5 步就能达到第 个点的情况。到达第 个点的至少步数必然是 5 步或者 6 步。

搞清楚性质之后，再回头看我们的状态定义：* 为到达第 个位置所需要的最少步数。*

因此当我们要求某一个 的时候，我们需要找到最早能够经过一步到达 点的 点。

即有状态转移方程： 。

也就是我们每次都贪心的取离 点最远的点 来更新 。

而这个找 的过程可以使用双指针来找。

因此这个思路其实是一个「双指针 + 贪心 + 动态规划」的一个解法。

Java 代码：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] f = new int[n]; 
        for (int i = 1, j = 0; i < n; i++) {
            while (j + nums[j] < i) j++;
            f[i] = f[j] + 1;
        }
        return f[n - 1];
    }
}

C++ 代码：

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 0);
        for (int i = 1, j = 0; i < n; i++) {
            while (j + nums[j] < i) j++;
            f[i] = f[j] + 1;
        }
        return f[n - 1];
    }
};

Python 代码：

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * n
        for i in range(1, n):
            j = 0
            while j + nums[j] < i:
                j += 1
            f[i] = f[j] + 1
        return f[-1]

• 时间复杂度：
• 空间复杂度：