0070. Climbing Stairs ===================== 题目信息 -------- :题号: 0070. 爬楼梯 :难度: Easy :主题: 动态规划、计数、斐波那契、矩阵快速幂 :原题: `LeetCode 0070 `_ :重点: 从枚举步长序列,推导到只保留相邻两个方案数,再用矩阵快速幂加速状态推进 题目重述 -------- 共有 ``n`` 级楼梯。每次只能向上走 1 级或 2 级,需要返回恰好到达第 ``n`` 级的不同走法数量。 走法由完整步长序列决定。只要两个序列中至少一个位置选择的步长不同,就视为两种不同走法。 约束条件: * ``1 <= n <= 45``。 自建示例 -------- * ``n = 1``:只有 ``1``,返回 ``1``; * ``n = 4``:走法为 ``1+1+1+1``、``1+1+2``、``1+2+1``、``2+1+1`` 和 ``2+2``,返回 ``5``; * ``n = 6``:到达第 6 级的方案数为到达第 5 级与第 4 级的方案数之和,即 ``8 + 5 = 13``; * ``n = 45``:返回 ``1836311903``,仍位于 32 位有符号整数范围内。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: struct Matrix { long long a00; long long a01; long long a10; long long a11; }; int plainRecursion(int step) { if (step <= 2) { return step; } return plainRecursion(step - 1) + plainRecursion(step - 2); } int memoDfs(int step, std::vector& memo) { if (step <= 2) { return step; } if (memo[step] != 0) { return memo[step]; } memo[step] = memoDfs(step - 1, memo) + memoDfs(step - 2, memo); return memo[step]; } int memoizedRecursion(int n) { std::vector memo(n + 1, 0); return memoDfs(n, memo); } int tableDp(int n) { if (n <= 2) { return n; } std::vector ways(n + 1, 0); ways[1] = 1; ways[2] = 2; for (int step = 3; step <= n; ++step) { ways[step] = ways[step - 1] + ways[step - 2]; } return ways[n]; } int rollingDp(int n) { if (n <= 2) { return n; } int previousTwo = 1; int previousOne = 2; for (int step = 3; step <= n; ++step) { const int current = previousOne + previousTwo; previousTwo = previousOne; previousOne = current; } return previousOne; } Matrix multiply(const Matrix& left, const Matrix& right) { return { left.a00 * right.a00 + left.a01 * right.a10, left.a00 * right.a01 + left.a01 * right.a11, left.a10 * right.a00 + left.a11 * right.a10, left.a10 * right.a01 + left.a11 * right.a11 }; } Matrix power(Matrix base, int exponent) { Matrix result{1, 0, 0, 1}; while (exponent > 0) { if ((exponent & 1) != 0) { result = multiply(result, base); } base = multiply(base, base); exponent >>= 1; } return result; } int matrixPower(int n) { if (n <= 2) { return n; } const Matrix transition{1, 1, 1, 0}; const Matrix factor = power(transition, n - 2); return static_cast(factor.a00 * 2 + factor.a01); } public: int climbStairs(int n) { return rollingDp(n); } }; 题解 ---- 最后一步分类 ~~~~~~~~~~~~ 设 ``ways(step)`` 表示恰好到达第 ``step`` 级的走法数量。任意完整走法的最后一步只有两种可能: * 从第 ``step - 1`` 级走 1 级; * 从第 ``step - 2`` 级走 2 级。 删除最后一步后,两类走法分别与到达 ``step - 1`` 和 ``step - 2`` 的走法一一对应。两类由最后步长区分,互不重叠,并覆盖全部合法走法,因此: .. code-block:: text ways(step) = ways(step - 1) + ways(step - 2) 基础状态为 ``ways(1) = 1`` 和 ``ways(2) = 2``。也可以定义 ``ways(0) = 1``,表示尚未迈步的空序列,此时同一转移从第 2 级开始成立。 递归搜索树 ~~~~~~~~~~ ``plainRecursion`` 直接按照最后一步分类递归计算。它准确表达了问题结构,但同一个级数会在不同分支中被反复求解。 例如计算 ``ways(5)`` 时,``ways(3)`` 同时出现在 ``ways(4)`` 与 ``ways(3)`` 两条分支中。随着 ``n`` 增大,重复子树快速增长,朴素递归的时间复杂度达到指数级。 状态结果复用 ~~~~~~~~~~~~ ``memoizedRecursion`` 为每个级数保存一次计算结果。第一次访问 ``ways(step)`` 时继续递归,之后再次访问同一状态时直接返回缓存值。 级数只可能位于 ``1`` 到 ``n``,因此最多计算 ``n`` 个不同状态。记忆化保留递归结构,同时把时间复杂度降为线性;代价是保存 ``O(n)`` 个结果以及递归调用栈。 自底向上填表 ~~~~~~~~~~~~ 递推只依赖更小级数,所以可以按 ``3, 4, ..., n`` 的顺序主动计算。``tableDp`` 使用 ``ways[step]`` 保存每一级的方案数,不再需要递归调用。 以 ``n = 6`` 为例: .. list-table:: :header-rows: 1 * - ``step`` - ``ways(step - 2)`` - ``ways(step - 1)`` - ``ways(step)`` * - 3 - 1 - 2 - 3 * - 4 - 2 - 3 - 5 * - 5 - 3 - 5 - 8 * - 6 - 5 - 8 - 13 填表顺序保证计算当前状态时,它依赖的两个状态已经完成。 滚动状态 ~~~~~~~~ 计算 ``ways(step)`` 只需要 ``ways(step - 1)`` 与 ``ways(step - 2)``。当前值生成后,更早的状态不会再参与后续转移,因此完整数组可以压缩为两个变量: * ``previousTwo`` 保存 ``ways(step - 2)``; * ``previousOne`` 保存 ``ways(step - 1)``; * ``current`` 保存两者之和。 更新时先计算 ``current``,再把旧的 ``previousOne`` 移到 ``previousTwo``,最后把 ``current`` 写入 ``previousOne``。这个顺序避免在使用旧状态之前将其覆盖。 ``rollingDp`` 与表格 DP 执行相同的状态转移,时间仍为 ``O(n)``,工作空间降为 ``O(1)``。公开入口选择这一方法,因为题目规模下它已经足够快,且状态含义直接。 矩阵状态推进 ~~~~~~~~~~~~ 递推可以写成矩阵形式: .. code-block:: text [ways(step) ] [1 1] [ways(step - 1)] [ways(step - 1)] = [1 0] [ways(step - 2)] 因此: .. code-block:: text [ways(n) ] [ways(2)] [ways(n - 1)] = T^(n - 2) [ways(1)] 其中 ``T = [[1, 1], [1, 0]]``。``matrixPower`` 使用二进制快速幂计算 ``T^(n - 2)``,把状态推进次数从 ``O(n)`` 降为 ``O(log n)``。 矩阵元素使用 ``long long`` 完成中间乘法。题目保证 ``n <= 45``,最终答案不超过 ``1836311903``,转换回 ``int`` 安全。 方法关系 ~~~~~~~~ 五种实现使用同一个最后一步递推,差异只在状态的计算与保存方式: * 朴素递归重复展开相同子问题; * 记忆化递归缓存每个级数; * 表格 DP 按级数顺序计算全部状态; * 滚动 DP 只保留当前转移需要的两个状态; * 矩阵快速幂把多次相同线性转移合并为幂运算。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 * - 朴素递归 - ``O(2^n)`` - ``O(n)`` 调用栈 * - 记忆化递归 - ``O(n)`` - ``O(n)`` * - 表格 DP - ``O(n)`` - ``O(n)`` * - 滚动 DP - ``O(n)`` - ``O(1)`` * - 矩阵快速幂 - ``O(log n)`` - ``O(1)`` 边界处理 ~~~~~~~~ * ``n = 1`` 时直接返回 ``1``; * ``n = 2`` 时直接返回 ``2``,无需进入递推循环; * 滚动循环从第 3 级开始,两个变量始终对应连续的前置状态; * 矩阵方法对 ``n <= 2`` 单独返回,避免出现负指数; * 约束上界确保所有答案均可由 ``int`` 表示。