动态规划（Dynamic Programming，简称 DP）是一种有效的算法设计思想，用于解决具有最优子结构和重叠子问题的复杂问题。其核心思想是通过记录已解决子问题的结果来避免重复计算，从而优化效率。关键在于定义问题的状态和状态转移方程。

​ 以下是塔子哥通过集合视角一步步推导状态和转移方程的详细过程。

step1:讨论 n = 4 的情况

对于 (n = 4)，所有可能的爬楼方式如下(5种)：

$0 \rightarrow 1 \rightarrow 2$$\rightarrow 3\rightarrow 4$

$0 \rightarrow 1 \rightarrow 2 \rightarrow 4$

$0 \rightarrow 1 \rightarrow 3 \rightarrow 4$

$0 \rightarrow 2 \rightarrow 3 \rightarrow 4$

$0 \rightarrow 2 \rightarrow 4$

将这些方案的集合定义为 $D_4$，那么集合的大小 $|D_4| = 5$ 就是问题的答案。

step2:情况分类

考虑到达第 4 级楼梯的方式，可以从两种途径到达：

1. 最后一步从第 3 级到达第 4 级，即 $3\rightarrow 4$
2. 最后一步从第 2 级到达第 4 级，即 $2\rightarrow 4$

根据这两种情况，我们可以将集合$D_4$分为两部分:

• $D_{4, 3 \rightarrow 4}$：最后一步从第 3 级到达第 4 级。
• $D_{4, 2 \rightarrow 4}$：最后一步从第 2 级到达第 4 级。

step3 : 等价映射

从集合划分可以观察到：

• $D_{4, 3 \rightarrow 4}$：将最后的 (4) 去掉，得到的方案等价于从 (0) 到 (3) 的所有方案，即 $|D_{4, 3 \rightarrow 4}| = |D_3|$。
• $D_{4, 2 \rightarrow 4}$：将最后的 (4) 去掉，得到的方案等价于从 (0) 到 (2) 的所有方案，即 $|D_{4, 2 \rightarrow 4}| = |D_2|$。

step4:递推方程

通过上述分析，可以得出递推关系：$|D_4| = |D_2| + |D_3|$

step5:推广情况

我们可以用相同的思路分析任意 (n)：要到达第 $n$ 级楼梯，最后一步只能是从 $n-1$ 或 $n-2$ 到达。因此，所有从 $0$ 到 $n$ 的方案可以表示为：

，这是爬楼梯问题的核心状态转移方程。

Step 6: 边界条件

在动态规划中，需要明确边界条件来初始化状态转移：

1. 从 (0) 到 (1) 的方案：只能 $0 \rightarrow 1$，因此：$|D_1| = 1$

2. 从 (0) 到 (2) 的方案：可以是 $0 \rightarrow 1 \rightarrow 2 或 0 \rightarrow 2$，因此：$|D_2| = 2$

step7:总结

1.状态定义：

$D_n$：从第 (0) 级楼梯到第 (n) 级楼梯的所有方案数。

2.状态转移方程：

$|D_n| = |D_{n-1}| + |D_{n-2}|$

3.边界条件： $|D_1| = 1, |D_2| = 2$

通过上述递推公式，可以高效地计算任意 (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个位置的值

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个位置的值
    }
}

c++代码

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

题目描述

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

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

输入

输入一个整数 n，表示楼梯的总级数。

输出

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

示例

输入 1

2

输出 1

2

输入 2

3

输出 2

3