困难

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

来源，leetcode 每日一题 45. 跳跃游戏 II

例如：

  1. 输入: [2,3,1,1,4]
  2. 输出: 2
  3. 解释: 跳到最后一个位置的最小跳跃数是 2。
  4.      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

解题思路

  1. 贪心的思路是很明显的。

    1. 从最后一个元素开始遍历，计算i位置的时候，只需要计算当前位置到前一个到达终点位置的最小移动次数就可以了，这种方式，最坏情况需要45. 跳跃游戏 II - 图1的复杂度。

    2. 从第一个元素开始，计算每一个位置可以到达的最远距离，什么时候更新步数呢？每次到达最远处时，进行一次更新，45. 跳跃游戏 II - 图2。

      代码

      对于第一种想法

      1. class Solution {
      2. public:
      3. int jump(vector<int>& nums) {
      4.   int n = nums.size();
      5.   vector<int> jump_vector(n, n);
      6.   jump_vector[n-1] = 0;
      7.   int min_index = n-1;
      8.   for (int i = n - 2; i >= 0; i--) {
      9.       if (min_index - nums[i] <= i) {
      10.           jump_vector[i] = jump_vector[min_index] + 1;
      11.       } else {
      12.           for (int j = min_index; j >= i; j--) {
      13.               if (j-nums[i] <= i) {
      14.                   jump_vector[i] = min(jump_vector[j] + 1, jump_vector[i]);
      15.               }
      16.           }
      17.           min_index = (jump_vector[min_index] > jump_vector[i] ? i : min_index);
      18.       }
      20.   }
      21.   return jump_vector[0];
      22. }
      23. };

      对于第二种想法

      1. class Solution {
      2. public:
      3. int jump(vector<int>& nums) {
      4.   int n = nums.size();
      5.   int steps = 0;
      6.   int max_positions = 0;
      7.   int end = 0;
      8.   for (int i = 0; i < n - 1; i++) {
      9.       max_positions = max(max_positions, i + nums[i]);
      10.       if (i == end) {
      11.           end = max_positions;
      12.           steps++;
      13.       }
      14.   }
      15.   return steps;
      16. }
      17. };