快速搭建网站模板 下载,建设机械网站方案设计,网贷代理推广,大连企业做网站公司排名❓剑指 Offer 10- II. 青蛙跳台阶问题
难度#xff1a;简单
一只青蛙一次可以跳上1级台阶#xff0c;也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e97#xff08;1000000007#xff09;#xff0c;如计算初始结果为#xff1a;1…❓剑指 Offer 10- II. 青蛙跳台阶问题
难度简单
一只青蛙一次可以跳上1级台阶也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e971000000007如计算初始结果为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 n0\\1\quad n1\\2\quad n2\\f(n-1)f(n-2)\quad n1\end{array}\right. f(n)⎩ ⎨ ⎧112f(n−1)f(n−2)n0n1n2n1
代码(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—力扣专栏每日更新 注 如有不足欢迎指正
