蓝桥杯试题 算法训练 进击的青蛙 python

资源限制
时间限制：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，所以开始我想使用递归的方法去求解，但是所写的代码只得了10分，其他都报运行错误，测试样例是通过的，没搞懂哪里出错了。
后来看到一个大佬的方法，属实是妙！大佬传送门
使用python实现相同思路，但是只拿到了90分，那位大佬的C++代码是可以拿到一百分的，下面代码有一个运行超时，不理解。

附上代码：

def jinji(dp,num):
    if dp[-1]==1:
        return "No Way!"
    dp[1] = 1 if dp[1]==0 else 0
    dp[2] = dp[1]+1 if dp[2]==0 else 0
    dp[3] = dp[2]+dp[1]+1 if dp[3]==0 else 0
    for i in range(4,num+1):
        if dp[i]==1:
            dp[i] = 0
        else:
            dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1000000007
    if dp[-1] == 0:
        return "No Way!"
    else:
        return dp[-1]
if __name__=="__main__":
    n= int(input())
    dp = [0]*(n+1)
    for i in range(1,n+1):
        dp[i] = int(input())
    print(jinji(dp,n))

最后

以上就是沉静果汁为你收集整理的蓝桥杯试题 算法训练 进击的青蛙 python的全部内容，希望文章能够帮你解决蓝桥杯试题 算法训练 进击的青蛙 python所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。