从牛客网上看到的这道题；题目如下：

一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米，如果为0，就会陷进去无法继续跳跃。河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1

输入描述:

输入分两行，第一行是数组长度N (1 ≤ N ≤ 10000)，第二行是每一项的值，用空格分隔。

输出描述:

输出最少的跳数，无法到达输出-1

输入

5

2 0 1 1 1

输出

4

这道题描述上，个人感觉不精致，比较曲折。目的就是要跳过数组的最后一位；过程中，依据当前所在位置的值k，可以向前走1~k步，到达下一个位置；且不能走到值为0的位置。

解这道题听心塞，从认为不存在最优子结构到最后双手赞同有最优子结构性质。（还需要多练习）

分析（以下图为例）

图中，描述了河里有5块石头（圆圈），每块石头有自己的编号（红色字体）和自身的数值（黑色字体），目的就是跳到最后的三角形（河岸）上。

假设存在最优解，即已经到三角形上了，那么最优路径上的最后一步，一定是通过三角形前面的第i块石头跳过来的。由图可知，能跳到三角形上的是第3块石头，和第4块石头。那么就存在子问题：到达第三块石头的最优解和到达第四块石头的最优解。子问题同原问题具有一样的结构，解题思路也就是一样的。最初条件是：初始站在第0块石头上。

由上面的分析，我们采用动态规划自底向上求解的思路，求到达河岸的最短跳跃次数。

package 牛客网;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main7_2{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = in.nextInt();
        }
        System.out.println(dtgh(n,arr));
    }
    /*
     * 在数组后增加一位，最终目的是跳到这一位置
     * 那么只要该位前面的某一位i能跳跃的距离超过最后一位，就一定能过河
     * 所以，求整体的最优变成求能跳到i的最优，以此类推
     */
    public static int dtgh(int n,int[] arr) {//动态规划
    	int[]res = new int[n+1];//用于存储跳到指定位置的最佳跳跃次数
    	res[0] = 0;
    	for(int k=1;k<=n;k++) {
    		int temp = Integer.MAX_VALUE;
	    	for(int i=0;i<k;i++) {
	    		if(arr[i]+i>=k && res[i]+1<temp) {
    				res[k] = res[i]+1;
    				temp = res[k];
    			}
	    	}
    	}
    	//System.out.println(Arrays.toString(res));
    	for(int i=1;i<=n;i++) {//除了第一位，其它出现0，说明掉河里了
    		if(res[i]==0)
    			res[n]=-1;
    	}
    	return res[n];
    }
}

纪实：这道题NG了好多次，直线拉低通过率。

1、开始理解错题目，认为脚下石头数值是多少就只能跳多远，还认为目的是跳到最后一块石头上；

2、后来把问题变成树结构，采用深度优先遍历，搜索所有路径，直接超时（毕竟深度不固定，暴力低效）

3、最后终于想明白了~