import java.util.Scanner;
public class Main {
static int max = Integer.MIN_VALUE;
public static void main(String[] args) {
// 使用动态的规划进行查看
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
System.out.println(dp(arr));
}
private static int dp(int[] arr) {
    // 创建一个dp数组用来记录每一个位置的最小步数
    int[] dp = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    dp[0] = 0;
    int n = arr.length;
    // 设计每每一个位置跳到的最小步数
    for (int i = 0; i < arr.length; i++) {
  // 如果出现 3 0 0 0 0 5 0 0 0 0 的情况就要排除，所以当前的dp[i]必须不等于最大值
        if(dp[i] != Integer.MAX_VALUE)for (int j = 0; j <= arr[i]; j++) {
            if (i + j <= arr.length - 1) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            } if (i + j > arr.length - 1) { // 如果当前的 加上可以向前跳的距离大于 河的长度直接返回 dp[i] + 1
                return dp[i] + 1;
            }
        }
    } // 最后进行判断，只要最后一个位置是的不等于int最大值并且arr[arr.length - 1] > 0 就返回dp[n - 1] + 1
    if (dp[n - 1] > 0 && arr[n - 1] != 0) {
        return dp[n - 1] + 1;
    } else {
        return -1;
    }
}

}

解：思路

当前跳板序号

当前跳板弹跳值

判断是否可以到对岸

是则到岸

否则判断跳到下个跳板后是否有机会过河（即前面力所能及的跳板弹跳值是否为全零）

是则输出-1

public class Main{

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);

        int arrLen = sc.nextInt();

        int[] arr = new int[arrLen];

        int[] dp = new int[arrLen];

        int minNum = Integer.MAX_VALUE;

        dp[0]=0;

        for(int i=1; i<dp.length; i++){

            dp[i] = Integer.MAX_VALUE;

        for(int i=0; i<arrLen; i++){

            arr[i] = sc.nextInt();

        }

        if(arr[0]==0){

            System.out.println(-1);

            return;

        }

            if(arr[i]!=0){

                for(int j=i+1; j<=Math.min(arr.length-1 , i+arr[i]); j++){

                    dp[j] = Math.min(dp[i]+1, dp[j]);

                }

                if(i+arr[i]>=dp.length){

                    minNum = Math.min(minNum, dp[i]+1);

                }

            }

        }

            if(dp[i]==Integer.MAX_VALUE){

                System.out.println(-1);

                return;

            }

        System.out.println(minNum);

    }

}

/**
 * 贪心
 */
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < a.length; i++)
            a[i]=i+sc.nextInt();    //i位置最远能到达的位置

        int step=1;
        int cur_max_i=a[0];//当前能到达的最远位置
        int max_i=a[0];//遍历过程中能到达的最远位置
        for (int i = 1; i < a.length; i++) {
            if (cur_max_i<i) {
                step++;
                //遍历过程中不能跳到比当前更远的位置了
                if (cur_max_i==max_i) {
                    System.out.println(-1);
                    break;
                }
                cur_max_i=max_i;
            }
            if (max_i<a[i]) {
                max_i=a[i];
            }
            //当前遍历过程中已经有能到达河对岸的位置了
            if (max_i>=a.length) {
                System.out.println(step+1);
                break;
            }
        }
        sc.close();
    }
}

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[] zhuangzi=new int[n];
             for(int i=0;i<n;++i)
                 zhuangzi[i]=in.nextInt();
             System.out.println(DynamicProgram(zhuangzi));
         }
    }
    
   public static int DynamicProgram(int[] dx)
   {
       int i,j,len=dx.length;
       int[] dp=new int[len+1];
       for(i=0;i<=len;++i)
           dp[i]=Integer.MAX_VALUE;
       dp[0]=0;
       if(dx[0]==0) return -1;
       for(i=0;i<len;++i) {
           if(dx[i]!=0)
           for (j = 1; j <= dx[i]; ++j)
           {
               if((i+j)<len&&dx[i+j]!=0&&dp[i]!=Integer.MAX_VALUE)
                   dp[i+j] = Math.min(dp[i+j],dp[i]+1);
               else if(i+j>=len&&dp[i]!=Integer.MAX_VALUE)
                   dp[len]=Math.min(dp[len],dp[i]+1);
           }

       }
       if(dp[len]==Integer.MAX_VALUE)
           return -1;
       else 
           return dp[len];
   }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i ++) {
                arr[i] = sc.nextInt();
            }
            int[] dp = new int[n + 1];
            for (int i = 0; i < n; i ++) {
                int endPosition = Math.min(i + arr[i], n);
                for (int j = i + 1; j <= endPosition; j ++) {
                    if(dp[j] == 0) dp[j] = dp[i] + 1;
                }
                if(dp[n] != 0 || (arr[i] == 0 && dp[i] == 0)) break;
            }
            if(dp[n] != 0) System.out.println(dp[n]);
            else System.out.println( - 1);
        }
    }
}

动态规划问题:

• 先将处在各个桩上时，能够跳跃的最大距离存储在数组 arrA 中。并且设置数组 arrB 存储到达此点时，需要最少需要跳跃的次数，初始化为Int型数组的最大值。 初始化 arrB[0] = 0，因为一开始就处在第一个桩上，不用跳跃。
  result 储存结果。
• 然后i从 0 开始遍历完数组 arrB，j 从 1 开始到arrA[i] 更新数组arrB[i+j]的值并且更新数组 arrB[i + j]，状态转移方程为

  arrB[i + j] = Math.min(arrB[i + j], arrB[i] + 1)

• 一旦确定了 i + j >= n 也就是跳到对岸时，得用result 和 arrB[i] + 1 比较，result并且取最小值。
• 得注意的是，可能遍历的 arrB[i] 存储的值为 Integer.MAX_VALUE，也就是之前的桩子不能跳跃到这条桩子上的，得用contine语句将后面语句结束掉，重新开始 i + 1 时的循环。

import java.util.Scanner; public class Main{ public static void main(String args[]){
        Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int arrA[] = new int[n]; int arrB[] = new int[n]; for(int i = 0; i < n; i ++){
            arrA[i] = scanner.nextInt();
            arrB[i] = Integer.MAX_VALUE;
        }

        arrB[0] = 0; int result = Integer.MAX_VALUE; for(int i = 0; i < n; i++){ if(arrB[i] == Integer.MAX_VALUE) continue; for(int j = 1; j <= arrA[i]; j++){ if(i + j >= n){
                    result = Math.min(arrB[i] + 1, result); break;
                }
                arrB[i + j] = Math.min(arrB[i + j], arrB[i] + 1);
            }
        } if(result == Integer.MAX_VALUE)
            result = -1;


        System.out.println(result);

    }
}

还是可以On的
import java.util.*;

public class Main {
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n;
    	int[] arr;
    	while(sc.hasNext()) {
    		n = sc.nextInt();
    		arr = new int[n];
    		for(int i = 0; i < n; i++) {
    			arr[i] = sc.nextInt();
    		}
    		int step = 0;
    		int cur = 0;
    		int next = 0;
    		for(int i = 0; i < n; i++) {
    			if(i > cur) {
    				if(next == 0) {
    					break;
    				}
    				cur = next;
    				next = 0;
    				step++;
    			}
    			next = Math.max(next, arr[i] == 0 ? 0 : arr[i] + i);
    			if(next >= n) {
    				break;
    			}
    		}
    		if(next == 0)
    			System.out.println(-1);
    		else
    			System.out.println(step + 1);
    	}
    }
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] num = new int[N + 1];
		for (int i = 0; i < N; i++) num[i] = sc.nextInt();
		num[N] = 1;//这是在陆地上了，不为0就可以了
		int[] dp = new int[N + 1];
		for (int i = 0; i <= N; i++) dp[i] = 10000;
		
		dp[0] = 0;
		for (int j = 1; j <= N; j++){
			if (num[j] == 0) continue;
			for (int i = 0; i < j; i++){
				if (num[i] >= j - i) dp[j] = Math.min(dp[i] + 1, dp[j]);
			}
		}
		
		System.out.println((dp[N] == 10000) ? -1 : dp[N]);//跳到陆地上最少需要的step

	}

}