70.爬楼梯｜三步破解动态规划核心奥秘

题意新解：

站在楼梯底仰望n级台阶，每步可选1或2阶，最终的路径组合犹如斐波那契数列般展开。比如到达第3阶的路径可由第1阶跨两步，或第2阶跨一步构成，这种递推规律揭示了两两相邻状态间的紧密关联。

思路解析：

采用‌动态规划‌策略，构建数组f存储子问题解：

1‌.状态定义‌：f[i]表示到达第i阶的方案数

2‌.边界条件‌：初始状态f[0]=1（平地不动）、f[1]=1（单步直达）

3‌.状态转移‌：循环计算f[i] = f[i-1] + f[i-2]，将问题分解为前一级和前两级的子问题之和

4‌.空间特性‌：线性数组存储中间结果，时间复杂度O(n)，空间复杂度O(n)

通过递推填充数组，最终直接返回f[n]，避免递归栈开销，通过表格记录保证每个状态仅计算一次。

注释代码：

class Solution {
public:
    int climbStairs(int n) {
        int f[100];          // 定义DP数组，预留足够空间（题目n≤45）
        f[0] = 1;            // 初始状态：0阶视为1种方案（数学定义需要）
        f[1] = 1;            // 边界条件：到达第1阶仅有1种走法
        
        for(int i = 2; i <= n; i++) {
            f[i] = f[i-1] + f[i-2];  // 状态转移：合并前两阶的可能性
        }
        
        return f[n];         // 返回第n阶的总方案数
    }
};