70. 爬楼梯

Bin大约 1 分钟

70. 爬楼梯

📝 题目描述

你正在爬楼梯，需要走到第 n 阶。

每次你可以爬 1 步 或 2 步。

问：到达第 n 阶有多少种不同的方法？

📌 示例

示例 1

输入：


n = 2

输出：

解释：

1 + 1
2

示例 2

输入：


n = 3

输出：

解释：

1 + 1 + 1
1 + 2
2 + 1

🚀 最优解：动态规划（Fibonacci 数列）

🔍 思路解析

爬到第 n 阶，可以有两种方式：

最后一步走 1 步：那之前在第 n-1 阶
最后一步走 2 步：那之前在第 n-2 阶

所以：


dp[i] = dp[i - 1] + dp[i - 2]

初始条件：


dp[0] = 1  （站在起点，有 1 种方式——不动）
dp[1] = 1  （只剩 1 阶，只能 1 步）

这就是斐波那契数列。

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取楼梯阶数
        int n = scanner.nextInt();

        // 创建解决方案对象并计算结果
        Solution solution = new Solution();
        int result = solution.climbStairs(n);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}