算法分析与设计►贪婪算法

Jump

  • 问题来源
  • 问题简介

    给你一个一维数组，数组的每个值表示当前能跳跃的距离，从0开始跳跃，问根据题给的数组跳到最后一位的最小距离。（假设我们总是能跳到最后一位的）。
    eg：
    A = [2, 3, 1, 1, 0]，从 0 开始，第一步可以跳到 1 和 2 位置，若我们选择跳到 1 的话，接下来能跳到的位置有 2、3、4，若我们跳到位置4，则到达目标位置，总步数为2。

解题思路


提出贪心算法：当前跳跃的距离取决于当前跳跃该距离之后能到达的最远距离，越大越好。
则有以下问题：

  • 第一步是否是安全的？

  • 该问题是否符合最优子结构？


证明：

  1. 若不走第二步能到达的最远距离的那一步s1，则第二步所能到达的任何一个点都能通过s1到达，故而该贪心算法的第一步是安全的。

  2. 是


时间复杂度 空间复杂度
O(未知) O(未知)

Code

class Solution {
public:
    int jump(vector<int>& nums) {
        return maximumJump(nums, 0, 0);
    }
    int maximumJump(vector<int>& nums, int cur, int step) {
        int val = nums[cur], maxIndex = cur, maxValue = val;
        int size = nums.size(), end = val + cur;
        if (cur == size - 1) {
            return step;
        }
        if (end >= size - 1) {
            return step + 1;
        }
        for (int i = cur + 1; i <= end; i++) {
            int dis = nums[i] + i - cur;
            if (dis > maxValue) {
                maxIndex = i;
                maxValue = dis;
            }
        }
        if (maxIndex == cur) {
            return -1;
        }
        return maximumJump(nums, maxIndex, step + 1);
    }
};

运行结果

Jump