蓝桥杯 算法提高 超级玛丽 （Java）

问题描述

大家都知道"超级玛丽"是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a1,a2,…am，陷入其中则必死无疑。显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。

 现在给出小道的长度n，陷阱的个数及位置。求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。

输入格式

第一行为两个整数n,m

　　第二行为m个整数，表示陷阱的位置

输出格式

一个整数。表示玛丽跳到n的方案数

样例输入

4 1

2

样例输出

1

数据规模和约定

40>=n>=3,m>=1

　　n>m;

陷阱不会位于1及n上

这个题的关键字为 回溯 递推 递归 但是应该说的是用他们三个任意都可以作出来吧，我用的是递归，样例一测是正确的，然后就提交了，是100分

我就想着用递归，说是有长为n的路，有m个陷阱，第二行是陷阱的所在地，我们就用一个数组来放陷阱的位置，然后递归每次只能走一步或两步，这个就和上台阶的问题是相似问题，只不过多了一个陷阱，那我们可以，加个参数，来等于我们每次不管是走一步还是两步的位置，在和我们刚才放位置的数组来比较，如果一样那就悄悄的返回（return），最后结束位置就是我们这个位置走到n,就给ans++（我们定义的一个用来每次走到n来给她进行++）还有就是如果我们所在的位置已经大于了n，那说明这是不行的，然后也悄悄的返回;代码如下

package 算法提高;
import java.util.Scanner;
public class Test165 {
  static int n,m;
  static int[] a;
  static int ans=0;
public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  n = scanner.nextInt();
  m = scanner.nextInt();
  a = new int[m];
  for (int i = 0; i < m; i++) {
    a[i]=scanner.nextInt();
  }
  f(1,a,0);
  System.out.println(ans);
}
private static void f(int i, int[] a, int j) {
  if (j>n) {
    return;
  }
  if (j==n) {
    ans++;
    return ;
  }
  for (int j2 = 0; j2 < m; j2++) {
    if (j==a[j2]) {
      return ;
    }
  }
  f(i+2, a, j=i+2);
  f(i+1, a, j=i+1);
}
}