刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

最少问题

题目描述：

河面上有N个木桩排成一排，且每个木桩上都有一个数字，木桩上的数字表示青蛙从当前木桩一次最多可跳跃的木桩个数（例如木桩上的数字为2，青蛙可以跳跃一个木桩也可以跳跃两个木桩）。请你帮助青蛙计算出从第一个木桩跳跃到最后一个木桩最少需要跳跃几次。

例如：N=5，5个木桩上的数字分别为2，1，5，1，3。

第一次跳跃，青蛙从第一个木桩跳跃到第三个木桩，共跳了2个木桩；

第二次跳跃，青蛙从第三个木桩跳跃到最后一个木桩，共跳了2个木桩；

故最少需要跳跃2次可到达最后一个木桩 。

输入描述

第一行输入一个正整数N（5≤N≤100），N表示河面上的木桩个数

第二行输入N个正整数（1≤正整数≤1000），表示每个木桩上的数字，正整数之间以一个空格隔开（输入的正整数顺序为木桩的排列顺序，第一个正整数为第一个木桩上的数字）

输出描述

输出一个整数，表示青蛙最少需要跳跃几次可到达最后一个木桩

样例输入

5
2 1 5 1 3

样例输出

2

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```#include #include #include using namespace std;int main() int N;cin >> N;vector nums(N);for (int i = 0; i < N; i++) {cin >> nums[i];}int max_jumps = 0;int curr_jumps = 0;int curr_pos = 0;while (curr_pos < N - 1) {int next_pos = curr_pos + nums[curr_pos];if (next_pos >= N - 1) {max_jumps++;curr_pos = N - 1;} else {int min_jumps = nums[curr_pos] + 1;for (int i = curr_pos + 1; i <= min(curr_pos + nums[curr_pos], N - 1); i++) {min_jumps = min(min_jumps, nums[i] + 1);}curr_jumps += min_jumps;max_jumps = max(max_jumps, curr_jumps);curr_pos = next_pos;}}cout << max_jumps << endl;return 0;```

解析：

【喵呜刷题小喵解析】：
该题是一个动态规划的问题，我们定义dp[i]为到达第i个木桩最少需要跳跃的次数，dp[N-1]即为所求。

我们可以从第一个木桩开始，逐步计算dp[i]。对于每个木桩i，我们可以从前面的木桩j跳跃过来，其中j的最大值为i-nums[i]。我们需要找到这样一个j，使得dp[j] + 1最小，因为青蛙从j跳跃到i需要跳跃一次。

因此，我们可以使用双指针的方法，一个指针j从i-nums[i]开始向前移动，另一个指针i从i开始向前移动。当i和j相遇时，我们找到了一个可以跳跃到i的木桩j，此时dp[i] = dp[j] + 1。

最后，我们只需要找到dp[N-1]即可。

在上面的代码中，我们使用了双指针的方法，其中curr_pos表示当前木桩的位置，next_pos表示从curr_pos跳跃后能够到达的最远位置。如果next_pos大于等于N-1，说明青蛙可以直接跳跃到最后一个木桩，此时max_jumps加1，curr_pos更新为N-1。否则，我们需要找到从curr_pos跳跃到next_pos的木桩，使得跳跃次数最少。我们使用一个变量min_jumps来记录最小的跳跃次数，然后遍历curr_pos到next_pos之间的木桩，更新min_jumps。最后，curr_jumps加上min_jumps，更新max_jumps和curr_pos。

最后输出max_jumps即可。
创作类型：
原创

本文链接：最少问题 题目描述： 河面上有N个木桩排成一排，且每个木桩上都有一个数字，木桩上的数字表示青蛙从当前

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share