题目描述：
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
数据范围：
$1\le nums.len \le 10^4, 0\le nums[i] \le 10^3$
题解：
贪心法：
当前区间为 $[i, maxx]$。可以找出该区间里最大的 $i + nums[i]$，以及他的下标 $index$。然后下次从这个下标开始，区间变成了 $[index, maxx + index + nums[index]]$。如果区间的右端点到达了 $n - 1$，直接返回次数就行。
动态规划：
假设 $dp[i]$ 表示从 $0$ 跳到 $i$ 所需要的最小步，可以遍历 $j + nums[j] \ge i$ 的所有 $j$，然后用 $dp[j]$ 更新 $dp[i]$。
复杂度比较高，但是也能过。可以考虑使用单调队列优化，使用一个单调增队列，每次取队首的最小值 $dp[q[hh]]$。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int jump(vector<int> &nums)
{
int n = nums.size();
int s = 0, maxx = nums[0];
if (maxx >= n - 1)
return 1;
int ans = 0;
while (true)
{
int mx = -1, index = -1;
for (int i = s; i <= maxx; ++i)
{
if (i + nums[i] > mx)
{
mx = i + nums[i];
index = i;
}
}
ans++;
maxx = mx;
s = index;
if (maxx >= n - 1)
return ans;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int jump(vector<int> &nums)
{
int n = nums.size();
vector<int> dp(n, INF);
dp[0] = 0;
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < i; ++j)
{
if (nums[j] + j >= i)
{
dp[i] = min(dp[j] + 1, dp[i]);
}
}
}
return dp[n - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int jump(vector<int> &nums)
{
int n = nums.size();
vector<int> dp(n, INF);
dp[0] = 0;
vector<int> q(n);
int hh = 0, tt = -1;
q[++tt] = 0;
for (int i = 1; i < n; ++i)
{
while (tt >= hh && i - q[hh] > nums[q[hh]])
++hh;
dp[i] = dp[q[hh]] + 1;
while (tt >= hh && dp[q[tt]] > dp[i])
--tt;
q[++tt] = i;
}
return dp[n - 1];
}
};
|