计蒜客题库

计蒜客题库题解系列:跳跃游戏(二)

题目测试地址:https://nanti.jisuanke.com/t/20

题目大意:

    给定一个非负整数数组,假定你的初始位置为数组第一个下标。数组中的每 个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标, 并且使用最少的跳跃次数。

例如:A=[2,3,1,1,4], 到达最后一个下标的最少跳跃次数为2(先跳跃1步, 从下标 0 到 1,然后跳跃 3 步,到达最后一个下标。一共两次)。

这一道题目根据不同的数据范围可以有不用的解法,本题中给出的数据范围是 n ≤ 100。可以直接利用最直观的动态规划的思想,用 dp[i] 表示到达第 i 个位置的最小步数,初始化第一个位置的 dp[1] 为 0,其他 dp 值记录为无穷大。从 1 位置开始扫描每,对于每个 i 位置,能更新后面的 dp 值,转移方程表示为

 

    有了转移方程以后,代码就很好写了。时间复杂度为


#include 
#include 
#include 
using namespace std;
const int mmax = 110;
int max_next[mmax];
int dp[mmax];
int main() {
    int n;
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &max_next[i]);
    }
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= max_next[i]; ++j) {
            dp[i + j] = min(dp[i + j], dp[i] + 1);
        }
    }
    printf("%d\n", dp[n - 1]);
    return 0;
}

 

对于n ≤ 100000 数据量,可以用线段树的方法,区间更新最小值。

最后对于 n 很大的情况,这道题还存在  的做法。需要用到单调队列。

3 comments

评论

你的邮箱地址并不会被公开显示 Required fields are marked *

你可以使用 HTML 标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>