几步可以从头跳到尾

    //首先计算当前最远可到达位置（记为cur），如果当前位置i已经在上一个最远可到达位置（pre），
    //说明下一步一定能够到达cur，此时steps加一，同时跟新pre的值。
    //七刷，这题思路太强了
        public int Jump (int n, int[] A) {
 
        //前一个最远可到达位置
        int pre=0;
        //当前最远可到达位置
        int cur=0;
        //步数
        int steps=0;
        //因为在pre处steps就加一，所以循环只需执行到索引n-2处  ???六刷时候没搞懂为啥n-1???
        for(int i=0;i<n-1;i++){
            cur=Math.max(cur,i+A[i]);
            //如果到达前一个最远可到达位置，说明下一步就可以到当前目标位置
            if(i==pre){
                pre=cur;
                steps++;
            }
        }
        return steps;
    }

function Jump( n ,  A ) {
    // write code here
    let end = 0, farthest = 0,stepNum = 0,len = A.length-1
    for(let i = 0;i<len;i++){
        farthest = Math.max(farthest, i + A[i])
        if(end>=n) break
        if(end == i){
            end = farthest
            stepNum++
        }
    }
    return stepNum
}

class Solution:
    def Jump(self , n: int, A: List[int]) -> int:
        # dp[i]表示到达i点的最小步数
        dp = [0]*n
        j = 0 
        for i in range(1, n):
            # 寻找能到达i点的最小j点
            while j + A[j] < i:
                j += 1 
            # 找到j点，更新dp
            dp[i] = dp[j] + 1 
        return dp[-1]

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少需要跳跃几次能跳到末尾
 * @param n int整型 数组A的长度
 * @param A int整型一维数组 数组A
 * @return int整型
*/
func Jump( n int ,  A []int ) int {
    var pre,cur,steps int
    for i,x:=range A{
        if i==n-1{
            break
        }
        cur=max(cur,i+x)
        if pre==i{
            pre=cur
            steps++
        } 
    }
    return steps
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

    public int Jump (int n, int[] A) {
        // write code here
        int[] f = new int[n];
        //贪心取j
        for (int i = 0, j = 0; i < n; i++) {
            f[i] = i;
            for (; j < i; j++) {
                if (A[j] + j >= i) {
                    f[i] = Math.min(f[i], f[j] + 1);
                    break;
                }
            }
        }
        return f[n - 1];
    }
//每次的j不需要从头开始，从上次位置开始即可，因为在此之间无法到达i，就必然无法到达i+1

class Solution:
    def Jump(self , n: int, A: List[int]) -> int:
        # write code here
        pre = 0#前一个最远可到达位置
        cur = 0#当前可达最远位置
        steps = 0#总步数
        for i in range(0,n):
            cur = max(cur,i+A[i])
            if(i == pre):
                pre = cur
                steps += 1
                if(pre>=n-1):
                    break
        #print(steps)
        return steps

    int Jump(int n, vector<int>& A) {
        // write code here
        //跳跃游戏
        int curDistance=0;
        int nextDistance=0;
        int res=0;
        for(int i=0;i<n;i++)
        {
            nextDistance=max(nextDistance,i+A[i]);
            if(curDistance==i)
            {
                if(curDistance==n-1)
                    break;
                else
                {
                    res++;
                    curDistance=nextDistance;
                    if(curDistance>=n-1) break;
                }
            }
        }
        return res;
    }

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 far = 0, count = 0, end = 0;
        for(int i = 0; i < n - 1; i ++){
            far = Math.max(far, i + A[i]);
            if(i == end){
                end = far;
                count ++;
            }
        }
        return count;
    }
}