过河问题,需要dp吗?每次能跳到的最远的地方,这样就能保证,跳跃次数最少了。感觉可以,但只过60%.
import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	while (in.hasNext()) {
    		int n = Integer.valueOf(in.nextLine());
    		String s = in.nextLine();
    		
    		if (n == 0) {
    			System.out.println(-1);
    			continue;
    		}
    		
    		String[] ss = s.split("\\s");
    		int[] a = new int[ss.length];
    		for (int i = 0; i < a.length; i++) {
    			a[i] = Integer.valueOf(ss[i]);
    		}
    		

    		
    		int count = 1;
    		int i = 0;
    		for (; i < a.length;) {
    			int step = a[i];
    			if (a[i] == 0) {
    				System.out.println(-1);
    				break;
    			}
    		
    			if (i + a[i] >= a.length) {
    				System.out.println(count);
    				break;
    			}
    			
    			int j = i + a[i];
    			for (; j > i && a[j] == 0; j--) {
    				
    			}
    			if (j == i) {
    				System.out.println(-1);
    				break;
    			} else {
    				i = j;
    				count++;
    			}
    		}
    		
    	}
    }
    


}