题解 | #几步可以从头跳到尾#

题意整理

• 给定一个数组A。
• 如果A数组中索引i对应值为t，说明可以从i处往后跳t步。
• 求从1出发跳到n，至少需要跳几次

方法一（从后往前贪心）

1.解题思路

基本思路是从后往前找能到达目标格子的前一个格子，然后在所有满足条件的格子中选择一个尽可能靠前的格子（贪心），找到之后，立即跟新目标格子的位置，并将步数加一，终止内层循环。

2.代码实现

import java.util.*;

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

        //初始化目标格子和步数
        int pos=n-1,steps=0;
        while(pos>0){
            //从前往后找能一步到pos的位置，找到就跳出循环
            for(int i=0;i<n;i++){
                if(i+A[i]>=pos){
                    //跟新目标格子pos，并将步数加一
                    pos=i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

3.复杂度分析

• 时间复杂度：最坏情况下，循环体需要执行 次，所以时间复杂度是 。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为 。

方法二（动态规划+贪心）

1.解题思路

• 初始化：定义一个长度为n+1的dp数组。
• 状态定义： 表示到达第i个格子至少需要的步数。
• 状态转移：为了到达i个格子步数最少，首先要确定前一个格子（记为j）在哪，可以通过贪心的方式找到j的位置，然后转移方程为 ，即从j位置往前再跳一次就到i位置。

动图展示：

2.代码实现

import java.util.*;

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

        //初始化dp数组，dp[i]表示到达第i个格子至少需要的步数
        int[] dp=new int[n+1];
        for(int i=2,j=1;i<=n;i++){
            //贪心地寻找到达第i个格子的前一步所在格子j
            while(j+A[j-1]<i){
                j++;
            }
            //从j位置跳一步到达i位置
            dp[i]=dp[j]+1;
        }
        return dp[n];
    }
}

3.复杂度分析

• 时间复杂度：在循环体中，每次i指针移动，j指针也会朝着i指针方向移动到附近的位置，从而最后j最多移动了n-1次，所以时间复杂度为 。
• 空间复杂度：需要额外大小为n+1的dp数组，所以空间复杂度为 。

方法三（从前往后贪心）

1.解题思路

首先计算当前最远可到达位置（记为cur），如果当前位置i已经在上一个最远可到达位置（pre），说明下一步一定能够到达cur，此时steps加一，同时跟新pre的值。

2.代码实现

import java.util.*;


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

        //前一个最远可到达位置
        int pre=0;
        //当前最远可到达位置
        int cur=0;
        //步数
        int steps=0;
        //因为在pre处steps就加一，所以循环只需执行到索引n-2处
        for(int i=0;i<n-1;i++){
            cur=Math.max(cur,i+A[i]);
            //如果到达前一个最远可到达位置，说明下一步就可以到当前目标位置
            if(i==pre){
                pre=cur;
                steps++;
            }
        }
        return steps;
    }
}

3.复杂度分析

• 时间复杂度：只需一层循环，所以时间复杂度为 。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为 。