解题思路

状态定义 设 dp(i) 表示到达第 i 级台阶的不同方法数，对应状态机的“节点”。

状态转移 要到达第 i 级，只可能从：

• i-1 级再走 1 步；
• i-2 级再走 2 步。

因此转移方程为：

边界条件

• dp(0)=1：表示不走台阶也算一种方式。
• dp(1)=1：只能一步到达第 1 级，只有 1 种方式。

这样从 0 开始，按照状态转移“走”到 n，累计所有路径数，就得到了最终答案。

实现代码

cpp

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入楼梯的级数

    // D 数组，D[i] 表示到达第 i 级台阶的方法数
    int D[n + 1];
    
    // 初始化
    D[1] = 1;  // 第 1 级台阶的方法数为 1
    D[2] = 2;  // 第 2 级台阶的方法数为 2

    // 递推
    for (int i = 3; i <= n; i++) {
        D[i] = D[i - 1] + D[i - 2];  // 根据递推公式
    }

    // 输出结果
    cout << D[n] << endl;

    return 0;
}

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取输入的整数n

        int[] dp = new int[n + 2];  // 初始化动态规划数组，长度为n+2，防止下标越界
        dp[1] = 1;  // 第1个位置的值设为1
        dp[2] = 2;  // 第2个位置的值设为2

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];  // 当前位的值等于前两位的和
        }

        System.out.println(dp[n]);  // 输出第n个位置的值
    }
}

python

n = int(input())  # 读取输入的整数n
dp = [0] * (n + 2)  # 初始化动态规划数组，长度为n+2，防止下标越界
dp[1] = 1  # 第1个位置的值设为1
dp[2] = 2  # 第2个位置的值设为2

for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]  # 当前位的值等于前两位的和

print(dp[n])  # 输出第n个位置的值

Leetcode 70.爬楼梯-原题链接

题目描述

小明正在爬楼梯。楼梯总共有 n 级台阶，小明每次可以选择爬 1 级或 2 级台阶。请问小明爬到第 n 级台阶的不同方法有多少种。

注意：假设小明从地面（第 0 级台阶）开始爬楼梯，每次可以从当前台阶选择爬 1 级或 2 级台阶，直到到达第 n 级台阶。

输入

输入一个整数 n（1 ≤ n ≤ 40），表示楼梯的总级数。

输出

输出一个整数，表示爬到第 n 级台阶的不同方法数。

示例

输入 1

2

输出 1

2

输入 2

3

输出 2

3