分析
-
本题的考点:动态规划、贪心。
-
本题本质上是一个最短路问题,可以将数组的每个位置看成一个点,从该点能跳到的位置连接一条有向边,我们在这个图中使用
BFS
求解最短路径即可得到答案,但是这样做的时间复杂度为$O(n ^ 2)$,对于本题会超时。需要考虑另外的做法。 -
使用
f[i]
表示从起点跳到数组nums
的下标为i
需要的最小步数,则我们可以发现数组f
一定是单调递增的,递增形式是阶梯状的(或者说f
是分段的,每隔一段就加1),后面的数据最多比前面相邻的一个数据多1。证明如下:
- 定义
j
为第一次到达i
的上一步的位置,则f[i] = f[j] + 1
。
代码
- C++
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
f[0] = 0;
for (int i = 1, j = 0; i < n; i++) { // 这里的j代表上一段,i代表下一段
while (j + nums[j] < i) j++; // 条件满足时,说明j跳不到i,需要j++
f[i] = f[j] + 1;
}
return f[n - 1];
}
};
- Java
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] f = new int[n];
f[0] = 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 for _ in range(n)]
j = 0
for i in range(1, n):
while j + nums[j] < i:
j += 1
f[i] = f[j] + 1
return f[n - 1]
时空复杂度分析
-
时间复杂度:$O(n)$,
n
为数组长度。 -
空间复杂度:$O(n)$。