算法题每日一练: 青蛙跳台阶
一、问题描述
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。求该青蛙跳上一个 n
(0 <= n <= 100)级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
二、题目要求
运行限制
最大运行时间:1s
最大运行内存: 128M
样例
复制代码
考察
复制代码
三、问题分析
做动态规划需要几步,就像冰箱装大象一样,分成三步:
第一步:含义搞懂
通常动态规划都会用数组 dp[]存放东西,那存放在数组里面的究竟是什么?
这要看题目问我们什么,这一题就问青蛙跳台阶的方案数嘛,那么 dp[i]就代表第 i 个台阶有 dp[i]个方案,它问什么我们就存什么。
第二步:变量初始
复制代码
初始变量一般找 2~5 个就行,下面才是重头戏啊!
第三步:关系归纳
搞清楚数组的含义和初始值之后,我们求的是第 n 个台阶方案数,题目又没给,怎么办?
找规律,做归纳总结,看看和前面的台阶方案有什么关系,这一步很重要,规律找不好直接芭比 q。
仔细看一下第二步的规律,后一个是不是等于前面两个相加,所以第 n 个公式为:
dp[n]=dp[n-1]+dp[n-2]。
三步走,打完收工!
四、编码实现
复制代码
五、测试结果
六、总结与提高
如果题目改成:
一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶......一直到 n 级台阶。求该青蛙跳上一个 n
(0 <= n <= 100)级的台阶总共有多少种跳法,做完之后可以在评论区交流结果
版权声明: 本文为 InfoQ 作者【知心宝贝】的原创文章。
原文链接:【http://xie.infoq.cn/article/a89d3d6a3550d50b5d56c8ae8】。文章转载请联系作者。
评论