力扣70题：告别暴力递归！从零实现记忆化搜索解法

题意解析：

想象你站在楼梯底部，面前有n级台阶。每次你可以选择跨1级或2级台阶，最终到达顶端的路径有多少种不同的走法？这个问题本质上是在探索分叉决策的叠加效果——当我们把每个台阶处的选择看作二叉树的分支，最终需要计算所有直达终点路径的叶子节点总数。

思路解析：

从顶层台阶逆向思考：到达第n阶的最后一步，可能是从n-1阶跨1级而来，或是从n-2阶跨2级而来。递归基例设定n=0或n=1时仅有1种走法（平地不动或单步直上）。通过数组a缓存子问题解，将暴力递归的指数复杂度优化至线性复杂度。每次递归先查询缓存，未命中时计算结果并存入数组，避免重复计算。

代码解析：

class Solution {
public:
    int a[46]; // 记忆化数组，题目约束n<=45
    
    Solution() // 构造函数初始化数组
    {
        for(int i=0;i<45;i++)
        {
            a[i]=0; // 初始标记为未计算状态
        }
    }

    int climbStairs(int n) {
        if(n==0 || n==1) // 基例：平地也算一种路径，单台阶仅一种走法
        {
            return 1;
        }
        if(a[n]==0) // 尚未计算过当前台阶的解
        {
            // 关键递推式：当前解=前一级台阶解+前两级台阶解
            a[n]=climbStairs(n-1)+climbStairs(n-2);
        }
        return a[n]; // 返回已缓存的结果
    }
};