正能量网站网址大全近期国际新闻热点大事件
❓剑指 Offer 10- II. 青蛙跳台阶问题
难度：简单
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
注意：本题与 70. 爬楼梯 相同。
💡思路：动态规划
当 n = 1 时，只有一种跳法：
当 n = 2 时，有两种跳法：
跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题，该问题的递推公式为：
f ( n ) = { 1 n = 0 1 n = 1 2 n = 2 f ( n − 1 ) + f ( n − 2 ) n > 1 f(n)=\left\{\begin{array}{rcc}1&\quad n=0\\1&\quad n=1\\2&\quad n=2\\f(n-1)+f(n-2)&\quad n>1\end{array}\right. f(n)=⎩ ⎨ ⎧112f(n−1)+f(n−2)n=0n=1n=2n>1
🍁代码：(C++、Java)
C++
class Solution {
public:int numWays(int n) {int ans = 1;int pre1 = 1, pre2 = 1;for(int i = 2; i <= n; i++){ans = (pre1 + pre2) % 1000000007;pre1 = pre2;pre2 = ans;}return ans;}
};
Java
class Solution {public int numWays(int n) {int ans = 1;int pre1 = 1, pre2 = 1;for(int i = 2; i <= n; i++){ans = (pre1 + pre2) % 1000000007;pre1 = pre2;pre2 = ans;}return ans;}
}
🚀 运行结果：
🕔 复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)，循环执行
n次，每次花费常数的时间代价，故渐进时间复杂度为 O ( n ) O(n) O(n)。 - 空间复杂度： O ( 1 ) O(1) O(1)，只用了常数个变量作为辅助空间。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！