最新青少年CSP考试必会之动态规划讲解(四)
2026-10-25 00:18:04
假设大楼里有这么一个楼梯，一共m阶，你现在奋力的往上爬楼梯，每次可以爬1或2个台阶。请问：一共有多少种不同的方法可以爬到楼顶呢？
示例分析示例 1：
输入：m = 2
输出：2
解释：有两种方法可以爬到楼顶。
第一步爬一阶，第二步爬一阶。
第一步爬两阶。
示例 2：
输入：m = 3
输出：3
解释：有三种方法可以爬到楼顶。
第一步爬一阶，第二步爬一阶，第三步爬一阶。
第一步爬一阶，第二步爬两阶。
第一步爬两阶，第二步爬一阶。
这个问题可以通过动态规划来解决。动态规划的核心思想是将问题分解为子问题，并存储子问题的解以避免重复计算。
定义状态：
设 dp[i] 表示爬到第 i 阶楼梯的方法数。
状态转移方程：
爬到第 i 阶楼梯的方法数可以从第 i-1 阶楼梯爬一步上来，或者从第 i-2 阶楼梯爬两步上来。
因此，状态转移方程为：dp[i] = dp[i - 1] + dp[i - 2]。
初始条件：
dp[1] = 1：只有一种方法，即爬一步。
dp[2] = 2：有两种方法，即爬两步一步或一步两步。
计算顺序：
从 i = 3 开始，依次计算 dp[i]，直到 dp[n]。
以下是基于上述思路的C++代码实现：
class Solution {public: int climbStairs(int n) { if (n <= 1) return n; vector<int> dp(n + 1); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }};代码解释初始条件处理：
如果 n <= 1，直接返回 n，因为只有一种方法（不爬或爬一步）。
初始化动态规划数组：
创建一个大小为 n + 1 的数组 dp，用于存储每个台阶的方法数。
设置初始值：
dp[1] = 1 和 dp[2] = 2，根据问题描述直接赋值。
填充动态规划数组：
从 i = 3 开始，根据状态转移方程 dp[i] = dp[i - 1] + dp[i - 2] 计算每个台阶的方法数。
返回结果：
最终返回 dp[n]，即爬到第 n 阶楼梯的方法数。
- 时间复杂度：O(n)，因为需要从 3 计算到 n。
- 空间复杂度：O(n)，因为使用了一个大小为 n + 1 的数组。
可以通过只存储前两个状态来优化空间复杂度到 O(1)：
class Solution {public: int climbStairs(int n) { if (n <= 1) return n; int prev1 = 1, prev2 = 2; for (int i = 3; i <= n; i++) { int current = prev1 + prev2; prev1 = prev2; prev2 = current; } return prev2; }};总结爬楼梯问题是一个经典的动态规划问题，通过定义状态、状态转移方程和初始条件，可以高效地计算出爬到第 n 阶楼梯的方法数。动态规划避免了重复计算，显著提高了效率。
热门标签
