跳跃游戏(三)

/*
这段代码就最后一个用例过不去，答案错误！！！！为什么！！！！
有没有大佬帮我看看哪里有问题啊！！
思路就是从前往后遍历，同时对一层循环的每个点的所有可达点进行遍历，更新最小跳跃步数；
如果更新时发现某一点是没有访问过的，就代表需要对其进行访问，也就是从当前点跳过去；
如果点是访问过的，就看这个点的访问路径，与从当前点跳过去的路径相比，哪个更短
*/
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] num = new int[n];
        int[] f = new int[n];
        int i;

        if (n == 1) {
            System.out.print(0);
            return;
        }

        for (i = 0; i < n; i++) {
            num[i] = in.nextInt();
        }
        f[0] = 0;
        for (i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n && j <= i + num[i]; j++) {
                f[j] = f[j] == 0 ? f[i] + 1 : Math.min(f[j], f[i] + 1);
            }
        }

        System.out.print(f[n-1]==0?-1:f[n-1]);
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {

    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    int res=0, right=arr[0], length=arr[0]; //在小于等于length的区域内都是1次可达
    for(int i=1; i<n; i++){
        if(arr[i]+i>right){ //更新可达的最远距离
            right = n-1>arr[i]+i? arr[i]+i : n-1; //右边界不能超过n-1，如果超过那么当i=n-1时可能直接跳过下一个判断条件（length=right>n-1），导致最终结果少一个
        }
        if(i==length){//当i来到了1次可达的最远距离更新结果
            res++; //已经遍历完一轮的可达距离
            // if(right==length) break; 右边界没有更新退出循环
            length = right; //下一次1次可达的区域最远为右边界
        }
    }
    if(length<n-1) cout<<-1; //如果遍历完了
    else cout<<res;

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] array = new int[n];
            for(int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            if(n == 0) {
                System.out.println(-1);
            } else {
                int res = jumpingGame(array);
                System.out.println(res);
            }
        }
    }
    public static int jumpingGame(int[] array) {
        int n = array.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < array.length - 1; i++) {
            int temp = array[i];
            if(dp[i] == Integer.MAX_VALUE || temp == 0) {
                continue;
            }
            // 更新跳到 i + 1, i + 2 ... i + temp 所需跳数,
            // 如果 i + temp 大于 n - 1, 那么只需要更新到 n - 1 即可
            for(int j = 1; j <= temp; j++) {
                if(i + j < n) {
                // 如果 i+j 位置所需跳数为 Integer.MAX_VALUE,
                // 直接更新为 dp[i] + 1,否则就取 max(dp[i+j],dp[i]+1)
                    if(dp[i + j] != Integer.MAX_VALUE) {
                        dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                    } else {
                        dp[i + j] = dp[i] + 1;
                    }
                } else {
                    break;
                }
            }
        }
        // 最后一个位置的状态如果不为 Integer.MAX_VALUE, 就直接返回,
        // 否则说明跳不到该位置, 返回 -1
        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }
}

Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n == 0) {
            System.out.println("-1");
            return;
        } else if (n == 1) {
            System.out.println("0");
            return;
        }
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        //从最后一个位置 往前标记 开始标记, 最少的跳跃的步数.. 0 表示到达不了.
        //每个位置 遍历可以到达的位置, 如果dp[i+j] >0; 跳跃步数记 dp[i] = dp[i+j] +1; 遍历完后,取最小值.
        int[] dp = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            int num = nums[i];
            for (int j = i + num; j >= i + 1; j--) {
                if (j >= n - 1) {
                    dp[i] = 1;
                    break;
                } else if (dp[j] > 0) dp[i] = dp[i] == 0 ? dp[j] + 1 : Math.min(dp[j] + 1, dp[i]);
            }
        }
        System.out.println(dp[0] == 0 ? -1 : dp[0]);

import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        int[]nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=sc.nextInt();
        }
        int edge=0,cur=0;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(i>edge){
               System.out.println(-1);
               return;
            }
             edge=Math.max(edge,nums[i]+i);
            if(cur==i&&i!=n-1){
                cnt++;
                cur=edge;
            }
           
        }
       System.out.println(cnt);
    }
}