蓝桥杯算法提高VIP-超级玛丽-题解\动态规划（Java代码）

解题思路:
最后一步i 可以来自前一步(i-1),和前两步(i-2),所以dp方程为 dp[i] = dp[i-1]+dp[i-2];

初始化：将数组全设置为 -1，然后 dp[1] = 1; 为陷阱的地方 为 0；

然后从 2 开始循环就可以了；

结果为 dp[n];
注意事项:
样例的陷阱大于 小道n的长度 ，会导致数组下标越界异常，。注意处理，
参考代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int[] dp = new int[n+1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		dp[1] = 1;
		
		for (int i = 1; i  n){ // 处理陷阱位置大于n；
				continue;
			}
			dp[s] = 0;
		}
		
		for (int i = 2; i < dp.length; i++) {
			if(dp[i] == 0) continue; // 陷阱处
			
			dp[i] = dp[i-1]+dp[i-2];//状态转移
			if(dp[i] < 0){
			 System.out.println(0); // 到不了终点
			 return;
		  }
		}
		
		System.out.println(dp[n]);
	}

}