每日算法 — 使用java实现爬楼梯：斐波那契动态规划与矩阵快速幂优化

问题描述

爬楼梯是一道经典的动态规划入门题。假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶？

这个问题看似简单，却蕴含了动态规划、递归、矩阵快速幂等多种算法思想，是理解递推关系的绝佳案例。

算法思路分析

方法一：递归（朴素解法）

设 f(n) 为爬到第 n 阶的方法数。由于每次只能跨 1 或 2 阶，所以：

f(n) = f(n-1) + f(n-2)

边界条件：f(0) = 1, f(1) = 1。这正是斐波那契数列的递推公式。

方法二：动态规划（记忆化搜索）

递归存在大量重复计算，时间复杂度为 O(2^n)。使用数组记录已计算的结果，可将复杂度降至 O(n)。

方法三：矩阵快速幂（最优解法）

斐波那契数列可用矩阵乘法表示：

| f(n)   |   | 1  1 |   | f(n-1) |
| f(n-1) | = | 1  0 | * | f(n-2) |

通过矩阵快速幂，可在 O(log n) 时间内求解，适用于 n 极大的场景。

Java 完整实现

public class ClimbingStairs {

    /**
     * 方法一：带记忆化的递归（自顶向下）
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    public int climbStairsMemo(int n) {
        int[] memo = new int[n + 1];
        return dfs(n, memo);
    }

    private int dfs(int n, int[] memo) {
        if (n <= 1) return 1;
        if (memo[n] != 0) return memo[n];
        // 状态转移：最后一步跨1阶或2阶
        memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo);
        return memo[n];
    }

    /**
     * 方法二：动态规划（自底向上）
     * 时间复杂度：O(n)，空间复杂度：O(n)
     */
    public int climbStairsDP(int n) {
        if (n <= 1) return 1;
        int[] dp = new int[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(1)
     */
    public int climbStairsOptimized(int n) {
        if (n <= 1) return 1;
        int prev2 = 1; // f(i-2)
        int prev1 = 1; // f(i-1)
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    /**
     * 方法四：矩阵快速幂
     * 时间复杂度：O(log n)，空间复杂度：O(1)
     * 利用斐波那契的矩阵表示进行快速幂运算
     */
    public int climbStairsMatrix(int n) {
        if (n <= 1) return 1;
        // 转移矩阵 [[1,1],[1,0]]
        long[][] base = {{1, 1}, {1, 0}};
        long[][] result = matrixPow(base, n);
        // result[1][0] 即为 f(n)
        return (int) result[1][0];
    }

    /**
     * 矩阵快速幂运算
     * @param matrix 底数矩阵
     * @param power  幂次
     * @return 矩阵的power次方
     */
    private long[][] matrixPow(long[][] matrix, int power) {
        // 初始化单位矩阵
        long[][] result = {{1, 0}, {0, 1}};
        long[][] base = matrix;
        while (power > 0) {
            // 如果当前位为1，累乘结果
            if ((power & 1) == 1) {
                result = matrixMultiply(result, base);
            }
            // 矩阵平方
            base = matrixMultiply(base, base);
            power >>= 1;
        }
        return result;
    }

    /**
     * 两个 2x2 矩阵相乘（对 MOD 取模防止溢出）
     */
    private long[][] matrixMultiply(long[][] a, long[][] b) {
        final long MOD = 1000000007L;
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }
        return c;
    }

    /**
     * 通用版本：每次可跨 1~k 阶台阶
     * 时间复杂度：O(n * k)，空间复杂度：O(n)
     */
    public int climbStairsGeneral(int n, int k) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        ClimbingStairs solution = new ClimbingStairs();
        int n = 10;

        System.out.println("=== 爬楼梯问题 (n=" + n + ") ===");
        System.out.println("记忆化递归: " + solution.climbStairsMemo(n));
        System.out.println("动态规划:   " + solution.climbStairsDP(n));
        System.out.println("空间优化:   " + solution.climbStairsOptimized(n));
        System.out.println("矩阵快速幂: " + solution.climbStairsMatrix(n));
        System.out.println("通用版本(k=3): " + solution.climbStairsGeneral(n, 3));

        // 测试大数情况
        int bigN = 50;
        System.out.println("\n大数测试 (n=" + bigN + "):");
        System.out.println("矩阵快速幂结果: " + solution.climbStairsMatrix(bigN));
    }
}

复杂度分析

扩展思考

1. 带花费的爬楼梯：每阶台阶有不同的体力消耗，求最小消耗到达顶部。
2. 不能连续跨两阶：增加约束条件，状态设计需要更精细。
3. 多步长变体：每次可跨 1~k 阶，递推式变为 f(n) = f(n-1) + ... + f(n-k)。

总结

爬楼梯问题通过斐波那契数列揭示了动态规划的核心思想：最优子结构与重叠子问题。从朴素的递归到矩阵快速幂的 O(log n) 解法，展示了算法优化的完整路径。掌握这一经典问题，是深入理解动态规划和矩阵运算的重要基石。