试题 算法训练 进击的青蛙

试题 算法训练 进击的青蛙

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　青蛙X正准备跳过一座桥，这座桥被划分为N段，记青蛙所在的起始点为0，桥的末端为N。桥上的一些点有一些石子，这些点是无法跳上去的。青蛙每次跳跃能向前跳跃+1，+2，+3段，现在请你算出跳到末端的总方法数。如果无法到达，请输出”No Way!"
输入格式
　　输入数据共N行。

第一行一个数字N，代表桥的长度。

接下来N行，表示从点1~N的道路情况，每行一个数字0或1，1表示有石子。
输出格式
　　输出一行，为一个整数，代表方法数，无法到达为“No Way!"
　　由于数据过大，我们只需要求出 对 1000000007 的余数即可
样例输入
5

1

0

0

1

0
样例输出
3
数据规模和约定
　　N <= 10^6
分析：跳步的话，我第一时间想到的是递归，加1，加2，加3，剔除不需要的不久就可以直接得到答案了吗，然后实践，可是时长太长了，没有能通过，不过答案是一样的，然后我看了一下大佬的方法，一个字：妙啊！直接通过数组，直接逐步向上，得出答案。
大佬链接：大佬

附上自己的代码：

#include<iostream>
using namespace std;
int  a[10000];
int way=0;
//定义递归函数,需要刚好跳到末端
int dfs(int m,int n)//m为步数，n为路的长度
{	
	if(a[m] == 1||m>n)//石头路走不了
	{
		return 0;
	}
	if (m == n)
	{	
		way++;//方法加一
		return way;
	}
    dfs(m+1, n);
	dfs(m+2, n);
	dfs(m+3, n);
}
int main()
{ int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{//开始铺路
		cin >> a[i];
	}
	dfs(0, n);//0点起步
	if (way == 0)
		cout << "NO Way";
	else
	cout << way<<endl;
	return 0;
}

运行结果：