题目

解法：动态规划

思路

核心思想是动态规划，发现到达每阶楼梯的方法数遵循斐波那契数列递推规律。

正确性基于分类加法计数原理：对于第i阶，最后一步只能是1阶或2阶。若最后一步为1阶，则有dp[i-1]种方法；若为2阶，则有dp[i-2]种方法。这两种情况互斥且穷尽所有可能，因此dp[i] = dp[i-1] + dp[i-2]成立。初始条件dp[1]=1和dp[2]=2可通过枚举验证，递推关系保证了所有子问题解的正确性。

实现步骤：

• Step 1: 初始化dp数组，设置dp[1]=1, dp[2]=2
• Step 2: 从i=3到n遍历，计算dp[i] = dp[i-1] + dp[i-2]
• Step 3: 返回dp[n]作为最终结果

复杂度

• 时间复杂度: $O(n)$，主要耗时在遍历计算每个台阶的方法数
• 空间复杂度: $O(n)$，使用了大小为n+2的数组存储中间结果

代码

class Solution {
public:
    int climbStairs(int n) {
        
        int dp[n+2];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};