2019-03-23 [蓝桥杯][算法提高VIP]超级玛丽

题目描述
大家都知道" 超级玛丽" 是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a1,a2,....am，陷入其中则必死无疑。显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。
现在给出小道的长度n，陷阱的个数及位置。求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。

数据规模和约定
40> =n> =3,m> =1
n> m;
陷阱不会位于1及n上

输入
第一行为两个整数n,m
第二行为m个整数，表示陷阱的位置
输出
一个整数。表示玛丽跳到n的方案数
样例输入
4 1
2
样例输出
1
提示
C语言在线学习平台微信号dotcpp
来源
算法提高

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100;
int m,n;
bool no[N];

void DFS(int dep,int&res)
{
    if(dep == n)
    {
        res++;
        return; 
    }
    else if(dep>n)
    {
        return ;    
    }   
    else
    {
        if(no[dep+1]==false) DFS(dep+1,res);
        if(no[dep+2]==false) DFS(dep+2,res);
    }
} 
int main(void) 
{
    int res=0,x;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        no[x]=true;
    }
    DFS(1,res);
    cout<<res; 
    return 0;
}