题目：青蛙过河

思路：动态规划

1. 当一块石头A可以被到达的前提是，前一块石头B可以通过跳跃k个单位到达，并且石头A可以通过在石头B跳跃k-1或k或k+1个单位到达
2. 因此，可以枚举每一个可以到达的石头并根据到达当前石头所使用的跳跃数更新下一个所能到达的石头
3. 最后统计最后一块石头是否能被到达即为答案
4. 可以观察到，跳跃的长度每次最多只能+1，因此最长的跳跃长度最大为n，n的大小为1000，因此可以使用n*n的数组模拟上述过程

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution14 {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		String[] s=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		s=br.readLine().split(" ");
		Map<Integer, Integer> map=new HashMap<Integer, Integer>();
		int[] stones=new int[n];
		for(int i=0;i<n;i++) {
			int t=Integer.parseInt(s[i]);
			//建立石头位置和下标的映射，可以快速找到下一跳的位置
			map.put(t, i);
			stones[i]=t;
		}
		//dp[i][j]的含义为到达下标为i的石头，是否可以通过在上一块石头跳跃j个单位到达
		boolean[][] dp=new boolean[n][n+1];
		//第一跳的长度固定为1，因此特判即可
		if(!map.containsKey(1)) {
			pw.println(false);
		}
		else {
			dp[1][1]=true;
			for(int i=1;i<n;i++) {
				for(int j=1;j<n;j++) {
					if(!dp[i][j]) {
						continue;
					}
					int nt=j-1;
					if(nt>0) {
						int st=stones[i]+nt;
						if(map.containsKey(st)) {
							dp[map.get(st)][nt]=true;
						}
					}
					nt=j;
					if(nt>0) {
						int st=stones[i]+nt;
						if(map.containsKey(st)) {
							dp[map.get(st)][nt]=true;
						}
					}
					nt=j+1;
					if(nt>0) {
						int st=stones[i]+nt;
						if(map.containsKey(st)) {
							dp[map.get(st)][nt]=true;
						}
					}
				}
			}
			boolean ans=false;
			for(int i=0;i<n;i++) {
				ans|=dp[n-1][i];
			}
			pw.println(ans);
		}
		pw.flush();
	}
}