题目

描述

• 给你一个长度为n的数组A。
  A[i]表示从i这个位置开始最多能往后跳多少格。
  求从1开始最少需要跳几次就能到达第n个格子。

方法一

思路

• 题目要求找出从1跳到n最快的路径，即所需步数最短，首先想到的就是遍历所有的路径，从中找出步数最短的路径，即为题目要求的从头跳到尾所需的步数。
• 对于f(i,n)函数，i表示当前所处的下标，i从1开始，n表示尾格子，A[i]为最多可以从第i个格子往后跳几步，则存在如下的递推公式：
  
  

具体步骤

• 1.判断所给数组是否为空，是否只有一个数，是则返回0，不是，执行步骤2；
• 2.判断是否可以从1直接跳到n，是，返回1，不是，则执行步骤3；
• 3.执行思路中的两个递推公式，求出最小的步数。
• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  *
  * 最少需要跳跃几次能跳到末尾
  * @param n int整型 数组A的长度
  * @param A int整型一维数组 数组A
  * @return int整型
  */
  public int Jump (int n, int[] A) {
     // write code here
     // 数组为空，或者长度为1，返回0
     if (A == null || A.length == 0 || A.length == 1){
         return 0;
     }
     // 能够从1开始直接跳到第n个格子
     if (1+A[0] >= n){
         return 1;
     }
     int res = 0;
     int[] dp = new int[n+1];
     // 假设从第n个格子到第n个格子所需步数为max，方便下面的循环运算
     dp[n] = Integer.MAX_VALUE;
     // 第n-1个格子到第n个格子的步数一定为1
     dp[n-1] = 1;
     int i = n - 2;
     while(i > 0){
         if (i + A[i-1] >= n){
             dp[i--] = 1;
             continue;
         }
         dp[i] = Integer.MAX_VALUE;
         // 实现递推公式
         for (int j = 1;j <= A[i-1]; ++j){
             dp[i] = dp[i] > dp[i+j] ? dp[i+j] : dp[i];
         }
         ++dp[i];
         --i;
     }
     return dp[1];
  }
  }

• 时间复杂度：，最坏情况A[i] = n-i-1，这样程序在计算时，每次循环需要比较n-i-1次,1+2+3+4+……+n-1=n*(n-1)/2，即；
• 空间复杂度：，使用一维数组dp辅助运算。

方法二

思路

• 方法一在运算过程中出现了运行超时的情况，无法完美解决问题，所以需要考虑对其进行优化，可以考虑使用贪心算法来降低时间复杂度。
• 从n节点往前逆推，找出最远的能够到达n点的节点（所贪的就是这个距离），每次都找最远的，当到达0点时，其所消耗的步数自然是最小的。

具体步骤

• 参考下图栗子：
  
• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  *
  * 最少需要跳跃几次能跳到末尾
  * @param n int整型 数组A的长度
  * @param A int整型一维数组 数组A
  * @return int整型
  */
  public int Jump (int n, int[] A) {
     // write code here
     int step = 0;
     // 数组为空，或者长度为1，返回0
     if (A == null || A.length == 0 || A.length == 1){
         return 0;
     }
     int reach = n-1;
     int index = 0;
     while(reach > 0){
         for (int i = 0; i < reach;++i){
             // 找到到达reach的最远点，更新
             if (i + A[i] >= reach){
                 reach = i;
                 ++step;
                 break;
             }
         }
     }
     return step;
  }
  }

• 时间复杂度：，对于全1的数组，其退化到；
• 空间复杂度：，常数级空间复杂度。

方法三

思路

• 方法二在全为1的情况下会退化至，因为在查找最远的能够到达n节点的点时，会找到第n-1个节点，再往下会找第n-2个节点……
• 所以可以考虑从左往右逼近终点，让我们先不考虑究竟要怎么走才能以最少的步数到达终点。
• 我们先从每一步来进行分析，首先假设我们现在处于index_j节点处，而当前的步长为A[index_j]，所以我们可以一步走到index_j ~ index_j + A[index_j]这个范围内的任意一个节点，假设我们走到了index+i点，即令index_i = index_j + i，此时其下一步的范围就在index_i ~ index_i + A[index_i]之间了，我们同样可以一步走到这个范围内的任意节点，这整个过程就好比是一颗树形成过程，参考下图示例：
  
• 那么现在我们有了一颗从0节点出发形成的m路树，可以看出，所求的最少步数也就是树的某一条从根节点到叶节点的最短路径。可以看见这棵树中有些冗余的部分，对其进行剪枝合并便得出下面的结果：
  
• 当然图中的3,4节点的路径计算结果是可以共用的，这里为了美观，所以画了两次。实际图放出来看一看吧：
  
• 也就是说我们不刻意的去找最少的步数的走法，而是一步一步往前走，每一步都尽量的使下一步能够到达更远的位置，当某一步能够到达的最远位置包括终点时，最短步数也就求出来了。
• 故我们可以从下标0位置开始遍历数组A，每次都计算当前节点能够到达的最远节点，并与遍历到现在的能够到达的最远节点进行比较，保留最大值，由于每一步的步长是受所处节点限制的，所以需要记录当前所处节点index，那么index ~ index + A[index]这个范围便是一个步长所能遍历的范围，当超过这个范围时，需要更新index为目前统计的所能够到达的最远位置，并进行下一个步长的遍历以及记录步长，遍历结束，即为所统计步长即为最短步长。
• 代码如下：

import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 最少需要跳跃几次能跳到末尾
* @param n int整型 数组A的长度
* @param A int整型一维数组 数组A
* @return int整型
*/
public int Jump (int n, int[] A) {

    // 步数
    int step = 0;
    // 数组为空，或者长度为1，返回0
    if (A == null || A.length == 0 || A.length == 1){
        return 0;
    }
    // 每走一步能够到达的最远位置
    int right = 0;
    // 当前这一步所处的位置
    int index = 0;
    // 遍历数组的指针
    int i = 0;
    int len = n-1;
    while(index < n && i < len){
        // 找出最远能够到达的位置
        right = Math.max(right,i + A[i]);
        // 遍历完了从index处能够走到的所有的位置
        // 走一步
        if (index == i){
            index = right;
            ++step;
        }
        ++i;
    }
    return step;
}
}

• 时间复杂度：，一层循环；
• 空间复杂度：，常数级空间复杂度。