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

动态规划—#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 ] d p[i]=d p[i-1]+d p[i-2] dp[i]=dp[i−1]+dp[i−2]

3. 初始条件：

• 爬到第 1 阶的方法只有一种， d p [ 1 ] = 1 \mathrm{dp}[1]=1 dp[1]=1 。

・爬到第2阶有两种方法， d p [ 2 ] = 2 d p[2]=2 dp[2]=2 (可以一次爬两阶，或者每次爬一阶)。

4. 边界条件:

• 当 n = 1 n=1 n=1 时，只有一种方法爬到楼顶，即直接爬 1 阶。
• 当 n = 2 n=2 n=2 时，有两种方法爬到楼顶，即一次爬两阶或者分两次爬 1 阶。

5. 迭代求解:

• 从第3阶开始，利用状态转移方程 d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] d p[i]=d p[i-1]+d p[i-2] dp[i]=dp[i−1]+dp[i−2] ，逐步计算到第 n n n 阶的方法数。

图解示例:

假设 n = 5 n=5 n=5 ，爬到楼顶的方法如下：

1. d p [ 1 ] = 1 \mathrm{dp}[1]=1 \quad dp[1]=1 (只能一步到 1 阶)
2. d p [ 2 ] = 2 \mathrm{dp}[2]=2 dp[2]=2 (可以 1 阶 +1 阶，或—次 2 阶)
3. d p [ 3 ] = d p [ 2 ] + d p [ 1 ] = 2 + 1 = 3 d p[3]=d p[2]+d p[1]=2+1=3 dp[3]=dp[2]+dp[1]=2+1=3

三种方法: 1 + 1 + 1 , 1 + 2 , 2 + 1 1+1+1,1+2,2+1 1+1+1,1+2,2+1

4. d p [ 4 ] = d p [ 3 ] + d p [ 2 ] = 3 + 2 = 5 d p[4]=d p[3]+d p[2]=3+2=5 dp[4]=dp[3]+dp[2]=3+2=5
5. d p [ 5 ] = d p [ 4 ] + d p [ 3 ] = 5 + 3 = 8 d p[5]=d p[4]+d p[3]=5+3=8 dp[5]=dp[4]+dp[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];
    }
};