NC68 跳台阶

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：0≤n≤40

要求：时间复杂度：$O(n)$ ，空间复杂度： $O(1)$

示例1

输入：

1
2

返回值：

1
2

说明：

1
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入：

1
7

返回值：

1
21

示例3

输入：

1
0

返回值：

1
0

思路：

  • 你可以想如果青蛙当前在第n级台阶上，那它上一步是在哪里呢？
  • 显然，由于它可以跳1级台阶或者2级台阶，所以它上一步必定在第n-1,或者第n-2级台阶，也就是说它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。
  • 设跳上 $i$级台阶有 $f(n)$ 种跳法，则它跳上n级的台阶有$f(n)=f(n-1)+f(n-2)$种跳法。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int jumpFloor(int target) {
        if (target<=1) return 1;
        int a = 1, b = 1, c = 0;
        for(int i = 2; i <= target; i++) {
            c = a+b;
            a = b;
            b = c;
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i-3];
        }
        return dp[n];
    }
}