【LeetCode】动态规划—爬楼梯（附完整Python/C++代码）

用户9613193

发布于 2026-06-16 19:36:39

470

动态规划—#70. 爬楼梯

前言
题目描述
基本思路
- 1. 状态定义：
- 2. 状态转移方程:
- 3. 初始条件：
- 4. 边界条件:
- 5. 迭代求解:
- 图解示例:
代码实现
- Python3代码实现
- C++代码实现

前言

“爬楼梯”问题是一个经典的动态规划问题，通常描述如下：假设有一个楼梯，总共有 n 级台阶。每次你可以选择爬 1 级或 2 级台阶。你需要计算出有多少种不同的方法可以爬到楼梯的顶部。

LeetCode是一个广受欢迎的在线编程平台，专注于算法和数据结构的练习。它提供了数千道编程题目，涵盖从简单到困难的各种难度，帮助程序员提升解决问题的能力，准备技术面试，并加深对计算机科学基础知识的理解。通过逐步解析不同类型的题目，希望能够帮助读者更好地理解算法的应用，掌握解题技巧，并提高编程能力。每篇文章将围绕特定的主题或算法展开，提供详细的解题思路以及代码实现。

题目描述

基本思路

这个问题是一个经典的动态规划问题，核心思想是通过递推计算爬楼梯的方法数。问题可以通过分析到达每一级台阶的方式进行分解。

1. 状态定义：

用 dp[i] 表示爬到第 i 阶楼梯有多少种不同的方法。

2. 状态转移方程:

从第 i 阶可以从 i-1 阶爬1步到达，也可以从 i-2 阶爬2步到达。
因此，爬到第 i 阶的方法数是爬到第 i-1 阶的方法数加上爬到第 i-2 阶的方法数：

d p[i]=d p[i-1]+d p[i-2]

3. 初始条件：

爬到第 1 阶的方法只有一种，

\mathrm{dp}[1]=1

。

・爬到第2阶有两种方法，

d p[2]=2

(可以一次爬两阶，或者每次爬一阶)。

4. 边界条件:

n=1

时，只有一种方法爬到楼顶，即直接爬 1 阶。

n=2

时，有两种方法爬到楼顶，即一次爬两阶或者分两次爬 1 阶。

5. 迭代求解:

从第3阶开始，利用状态转移方程

d p[i]=d p[i-1]+d p[i-2]

，逐步计算到第

阶的方法数。

图解示例:

假设

n=5

，爬到楼顶的方法如下：

\mathrm{dp}[1]=1 \quad

(只能一步到 1 阶)

\mathrm{dp}[2]=2

(可以 1 阶 +1 阶，或—次 2 阶)

d p[3]=d p[2]+d p[1]=2+1=3

三种方法:

1+1+1,1+2,2+1

d p[4]=d p[3]+d p[2]=3+2=5

d p[5]=d p[4]+d p[3]=5+3=8

代码实现

Python3代码实现

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        # 初始化dp数组，用来保存每个台阶的方法数
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        # 从第3个台阶开始，根据递推公式计算方法数
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

# 示例测试
sol = Solution()
print(sol.climbStairs(2))  # 输出: 2
print(sol.climbStairs(3))  # 输出: 3

C++代码实现

class Solution {
public:
    int climbStairs(int n) {
        // 如果楼梯数小于等于2，直接返回结果
        if (n <= 2) return n;
        
        // 使用动态规划，dp[i] 代表爬到第 i 阶的方法数
        int dp[n + 1];
        dp[1] = 1;  // 只有1种方法爬到第1阶
        dp[2] = 2;  // 有2种方法爬到第2阶

        // 通过递推公式 dp[i] = dp[i - 1] + dp[i - 2] 计算
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        // 返回爬到第 n 阶的方法数
        return dp[n];
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-06-16，如有侵权请联系 cloudcommunity@tencent.com 删除

python