本文系统解析力扣70题爬楼梯问题的动态规划解法，通过递推公式推导、状态转移方程构建、边界条件分析等步骤，详细讲解如何用C++实现高效解法。文章包含完整的代码实现、时间复杂度分析及空间优化技巧，并通过测试案例验证解法的正确性。

一、问题理解与建模

力扣70题爬楼梯问题要求计算到达n阶楼梯的不同方法数。假设每次可以爬1或2个台阶，该问题本质上是求斐波那契数列的第n+1项。动态规划（将复杂问题分解为简单子问题的算法思想）是该问题的标准解法，其核心在于发现重叠子问题和最优子结构特性。

为什么选择动态规划？因为当n≥3时，到达第n阶的方法数等于到达第n-1阶和n-2阶方法数之和。这种重复计算的特性使得暴力递归解法会产生指数级时间复杂度，而动态规划通过存储中间结果实现效率优化。

二、动态规划三要素分析

定义dp数组的含义是解题关键。令dp[i]表示到达第i阶楼梯的方法总数，则状态转移方程可表示为：dp[i] = dp[i-1] + dp[i-2]。这个递推公式完美体现了问题的最优子结构特性。

边界条件的处理直接影响算法正确性。初始状态需明确：dp[0]=1（地面状态），dp[1]=1（第一阶）。当n≥2时，通过迭代计算填充dp数组。这个过程有效避免了递归解法的重复计算问题。

三、代码实现与测试验证

测试案例演示

    输入n=5时，代码应返回8种方法。验证过程如下：
    dp[2] = 1+1=2
    dp[3] = 2+1=3
    dp[4] = 3+2=5
    dp[5] = 5+3=8
    以下C++实现严格遵循动态规划范式：
    int climbStairs(int n) {
        if(n <= 1) return 1;
            int dp[n+1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i=2; i<=n; ++i) {
                dp[i] = dp[i-1] + dp[i-2];
        }
    return dp[n];
    }

四、时间复杂度与空间优化

基础解法时间复杂度为O(n)，空间复杂度同为O(n)。但观察状态转移方程可知，当前状态仅依赖前两个状态，因此可将空间优化至O(1)：

    int climbStairs(int n) {
    if(n <= 2) return n;
    int a=1, b=2, c;
    for(int i=3; i<=n; ++i){
        c = a + b;
        a = b;
        b = c;
    }
    return b;
    }

五、不同解法的对比分析

递归解法时间复杂度为O(2^n)，当n=40时计算次数超过万亿次。动态规划将时间复杂度降至线性级别，空间优化版本更是仅需常量空间。矩阵快速幂解法可将时间复杂度进一步降至O(logn)，但实现复杂度较高，适合理论研究。

如何处理n=0的特殊情况？根据问题定义，当n=0时应该返回1，这对应着"不移动"这种特殊状态。代码中通过边界条件判断确保了这个情况的正确处理。

本文完整呈现了力扣70题的动态规划求解过程，从问题建模到代码优化层层递进。通过状态转移方程推导、空间复杂度优化、测试用例验证等环节，展示了标准算法题的规范解法。该解法时间复杂度O(n)、空间复杂度O(1)，是兼顾效率与实现难度的最优方案。