JZ69 跳台阶

发表于 分类于 本文字数： 471 阅读时长 ≈ 2 分钟

JZ69 跳台阶

描述

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

数据范围：$1≤n≤40$

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

示例1

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

示例2

1
2
输入：7
返回值：21

题解

做完JZ42和JZ85，现在至少会拆解子问题了。对这道题来说，跳到$i$层时，假定已经有$dp[i]$种跳法，若是跳到$i+1$层，则有$dpi-1+dpi$种跳法，由此可以得到状态转换方程：
$$
dp[i]=dp[i-1]+dp[i-2]
$$
边界状态：

1
2
dp[1]=1	跳一层只有一种跳法
dp[2]=2 跳两层只有两种跳法

一遍过了，问了大G老师优化的方式，首先是可以通过和JZ42、JZ85的同样的优化方式，把递归写成循环然后记录$pre$，把空间复杂度优化到$O(1)$。其次是可以在递归的同时，使用一个全局数组来记录每次计算的方式，相当于剪枝了，直接递归每个$i$会计算两次，这样优化过后则只需要计算一次即可，但空间复杂度仍然是$O(n)$，一部分来自于递归栈，另一部分来自于额外开辟的存储空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 
     * @return int整型
     */
    int jumpFloor(int number) {
        if(number == 1) return 1;
        if(number == 2) return 2;
        return jumpFloor(number-2)+jumpFloor(number-1);
    }
};