L9-最小跳跃次数

LeetCode

发布日期: 2022-04-16

LCP 09. 最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。

为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：

输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

method 1: BFS

如果去遍历0到idx的节点会超时，所以用一个变量preidx记录之前已经被更新的节点，因为BFS中更新的节点都是最短路，所以只需要更新preidx到idx之间没被更新过的节点就可以了

int minJump(vector<int>& jump) {
    int n = jump.size();
    vector<bool> used(n, false);
    queue<pair<int, int>> q;
    q.push({0, 0});
    used[0] = true;
    int preidx = 1;
    while (!q.empty()) {
        auto [idx, dist] = q.front();
        q.pop();
        int next = idx + jump[idx]; // 向前跳
        if (next >= n) {
            return dist + 1;    // 跳出就返回
        }
        if (!used[next]) {
            used[next] = true;
            q.push({next, dist + 1});
        }
        while (preidx < idx) {  // [preidx,idx)之间未更新的点
            if (!used[preidx]) {
                used[preidx] = true;
                q.push({preidx, dist + 1});
            }
            preidx++;   // 更新了就递增
        }
    }
    return -1;
}

mehod 2: 动态规划

dp[i]：表示从当前位置i可以跳出去的最小次数

对于位置i，可以向前跳

如果i+jump[i]>=n，说明从当前位置跳1步就可以出去了，所以dp[i]=1
否则，只能先跳到i+jump[i]的位置再看，所以dp[i]=dp[i+jump[i]]+1

对于位置i+1到n-1的位置（用j来表示），都可以向后跳到i的位置，所以如果dp[i]+1比原来的dp[j]小的话就可以更新dp[j]，表示从位置j先跳1步到i，再从i跳dp[i]步跳出去

int minJump(vector<int>& jump) {
    int n = jump.size();
    vector<int> dp(n);
    for (int i = n - 1; i >= 0; i--) {
        if (i + jump[i] >= n) dp[i] = 1;
        else dp[i] = dp[i + jump[i]] + 1;
        for (int j = i + 1; j < n; j++) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }
    return dp[0];
}