题解

题面描述

给定一个整数 $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$）。

这实际上就是斐波那契数列的变形，时间复杂度为 $O(n)$，空间复杂度可以降到 $O(1)$。

代码分析

• 变量说明

  • $dp1$：表示前一阶的方法数，即 $dp[i-2]$。
  • $dp2$：表示当前阶的方法数，即 $dp[i-1]$。
  • $dp$：临时变量，用来存储 $dp1 + dp2$ 得到的 $dp[i]$。

• 递推过程
  从 $i = 3$ 开始，每一步将 $dp[i]$ 计算出来，然后更新 $dp1$ 和 $dp2$，直到 $i = n$。

• ACM 模式
  主函数中使用标准输入输出，保证能够正确处理输入输出。

C++

#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;
}

Python

# 定义 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))

Java

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();
    }
}

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$