假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入一个整数n表示需要n阶你才能到达楼顶。
输入
2
输出
2
有两种方法可以爬到楼顶。
输入
3
输出
3
有三种方法可以爬到楼顶。
给定一个整数 n，表示到达楼顶需要经过 n 阶台阶。每次你可以选择爬 1 阶或 2 阶。求有多少种不同的方法可以爬到楼顶。
本题可以采用动态规划来解决。设 dp[i] 表示爬到第 i 阶的方法数，有如下递推公式：
这实际上就是斐波那契数列的变形，时间复杂度为 O(n)，空间复杂度可以降到 O(1)。
变量说明
递推过程
从 i=3 开始，每一步将 dp[i] 计算出来，然后更新 dp1 和 dp2，直到 i=n。
ACM 模式
主函数中使用标准输入输出，保证能够正确处理输入输出。
#include <iostream>
using namespace std;
// 使用 Solution 类包装功能函数，符合 LeetCode 风格
class Solution {
public:
// 函数功能：计算爬楼梯的方法数
int climbStairs(int n) {
// 如果 $n$ 小于等于 2，直接返回 $n$
if(n <= 2) return n;
// 初始化 dp 数组中的前两个状态
int dp1 = 1; // 对应 $dp[1]$
int dp2 = 2; // 对应 $dp[2]$
// 从 $i = 3$ 开始进行状态转移
for(int i = 3; i <= n; i++){
int dp = dp1 + dp2; // 状态转移方程 $dp[i] = dp[i-1] + dp[i-2]$
dp1 = dp2; // 更新 $dp[i-2]$
dp2 = dp; // 更新 $dp[i-1]$
}
return dp2; // 返回 $dp[n]$
}
};
int main(){
int n;
// 读取输入的阶数
cin >> n;
Solution sol;
// 输出结果
cout << sol.climbStairs(n) << endl;
return 0;
}
# 定义 Solution 类，封装爬楼梯的方法
class Solution:
def climbStairs(self, n: int) -> int:
# 如果 $n$ 小于等于 2，直接返回 $n$
if n <= 2:
return n
dp1, dp2 = 1, 2 # 分别对应 $dp[1]$ 和 $dp[2]$
# 从 $i = 3$ 开始，进行动态规划状态转移
for i in range(3, n + 1):
dp = dp1 + dp2 # $dp[i] = dp[i-1] + dp[i-2]$
dp1, dp2 = dp2, dp # 更新状态
return dp2
if __name__ == "__main__":
# 读取输入的阶数
n = int(input())
sol = Solution()
# 输出结果
print(sol.climbStairs(n))
import java.util.Scanner;
// 主类，包含 ACM 模式的输入输出
public class Main {
// 定义 Solution 类，封装爬楼梯的方法
static class Solution {
public int climbStairs(int n) {
// 如果 $n$ 小于等于 2，直接返回 $n$
if (n <= 2) return n;
int dp1 = 1; // 对应 $dp[1]$
int dp2 = 2; // 对应 $dp[2]$
// 从 $i = 3$ 开始进行状态转移
for (int i = 3; i <= n; i++) {
int dp = dp1 + dp2; // 状态转移方程：$dp[i] = dp[i-1] + dp[i-2]$
dp1 = dp2; // 更新 $dp[i-2]$
dp2 = dp; // 更新 $dp[i-1]$
}
return dp2; // 返回 $dp[n]$
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入的阶数
int n = sc.nextInt();
Solution sol = new Solution();
// 输出结果
System.out.println(sol.climbStairs(n));
sc.close();
}
}