题⽬
⼀只⻘蛙⼀次可以跳上1级台阶，也可以跳上2级。求该⻘蛙跳上⼀个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
示例1 输⼊：2 输出：2 解释：⻘蛙要跳上两级台阶有两种跳法，分别是：先跳⼀级，再跳⼀级或者直接跳两级。因此答案为2
示例2 输⼊：7 输出：21
示例3： 输⼊：0 输出：0
思路及解答
动态规划
这题和第7题 斐波那契数列 基本类似，只是换了一个题目表达方式。
青蛙跳到第n级台阶的跳法数 dp[i] 取决于两种最后一步的选择：
从第
i-1级跳1级：跳法数为 dp[i-1]从第
i-2级跳2级：跳法数为 dp[i-2]
使用数组 dp，其中 dp[i] 表示跳到第 i 级台阶的跳法数
状态转移： dp[i] = dp[i-1] + dp[i-2]，初始化 dp[1] = 1，dp[2] = 2
时间复杂度
O(n)空间复杂度
O(n)
动态规划（滚动数组优化）
观察状态转移方程，发现当前状态仅依赖前两个状态（dp[i-1] 和 dp[i-2]），因此只需保存这两个值，无需存储整个数组
时间复杂度
O(n)空间复杂度
O(1)
如何思考空间优化方法？
观察状态依赖： 确认当前状态是否仅依赖有限的前几个状态（如斐波那契数列仅依赖前两项）
变量替换： 用固定数量的变量替代数组，滚动更新这些变量
边界处理： 初始化时需明确前几个状态的初始值（如
f(1)和f(2)）