题解 | #跳台阶#
跳台阶
https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4
描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
数据范围：1 \leq n \leq 401≤n≤40
要求：时间复杂度：O(n)O(n) ，空间复杂度： O(1)O(1)
示例1
输入：
2复制
返回值：
2复制
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2
示例2
输入：
7复制
返回值：
21复制
解题思路：
dp[i]表示跳i个台阶的跳法总和
那么怎么才能跳到第i个台阶呢？有两种方式
1）从i-1处跳1个台阶跳到i；
2）从i-2处跳2个台阶跳到i；
方法总数即为上面两种方法的和。
base case
dp[0]=0
dp[1]=1
dp[2]=2
class Solution {
public:
int jumpFloor(int number) {
vector<int>dp(number+1); //dp[i]表示跳i个台阶的跳法总和
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= number; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[number];
}
};
投递美团等公司9个岗位
