博客

首先应当指出，这道题的问题描述不清晰。描述中说到：河中间打了很多桩子，每隔一米就有一个，河流一共n米宽，袋鼠初始在第一个弹簧上面，若跳到最后一个弹簧就算过河了。 结合题目中给出的样例，疑点有以下两个：

（1）n米宽的河，每隔一米打一个桩，为什么一共打了n个桩，是起点没打桩还是终点没打桩？

（2）分析输入样例，容易知道满足最少跳数的路线是这样的：2—>第一个1—>第二个1—>最后一个1。得到最少跳数为3，与样例输出的4不符。

抛开这些疑点不谈，这道题目中的DP思想还是值得去探讨研究的。

思路：用dp[i]代表到达i位置时的最小步数，而dp[i]又和前面的位置有关，如果j+a[j]>=i,就说明j位置能到达i位置，就更新dp[i]，保存到达的最小步数

对问题进行抽象之后，得到递推方程如下（其中dp数组存储了袋鼠跳跃的最小步数，初值为0）：

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

Java源代码如下：

import java.util.*;

public class Main  {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] a=new int[n+1],dp=new int[n+1];//a[i]表示第i个桩的弹簧力量，dp[i]表示到第i个桩的最小跳数
        for(int i=1;i<=n;i++){
        	a[i]=in.nextInt();
        }
        for(int i=2;i<=n;i++)
        	dp[i]=10000;//初始值为最大跳数
        for(int i=2;i<=n;i++){
        	for(int j=1;j<i;j++){
        		if(j+a[j]>=i){//如果从第j个桩能一下子跳到第i个桩
        			dp[i]=Math.min(dp[i],dp[j]+1);//更新dp
        		}
        	}
        }
        System.out.println(dp[n]==10000?-1:dp[n]+1);
        //这样写是为了贴合样例，正确的写法应当是System.out.println(dp[n]==10000?-1:dp[n]+1);
    }
}