题解

题面描述

给定一个整数 $n$，表示到达楼顶需要经过 $n$ 阶台阶。每次你可以选择爬 $1$ 阶或 $2$ 阶。求有多少种不同的方法可以爬到楼顶。

思路

本题可以采用动态规划来解决。设 $dp[i]$ 表示爬到第 $i$ 阶的方法数，有如下递推公式：

• 当爬到第 $i$ 阶时，上一步可能从第 $i-1$ 阶迈一步上来，也可能从第 $i-2$ 阶跨两步上来，因此有：$$dp[i] = dp[i-1] + dp[i-2]$$
• 初始条件：$dp[1] = 1$，$dp[2] = 2$（当 $n\le2$ 时直接返回 $n$）。

Leetcode 81.爬楼梯-原题链接

题目内容

假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。

每次你可以爬 $1$ 或 $2$ 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入描述

输入一个整数$n$表示需要$n$阶你才能到达楼顶。

输出描述

样例1

输入

2

输出

2

说明

有两种方法可以爬到楼顶。

1. $1$ 阶 + $1$ 阶
2. $2$ 阶

样例2

输入

3

输出

3

说明

有三种方法可以爬到楼顶。

1. $1$ 阶 + $1$阶 + $1$ 阶
2. $1$ 阶 + $2$阶
3. $2$ 阶 + $1$ 阶

提示

• $1 <= n <= 45$