爬楼梯问题【多解法】

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注：n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

方法一：暴力法

在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。而在每一步中我们都会继续调用 climbStairs，climbStairs 这个函数模拟爬 1 阶和 2 阶的情形，并返回两个函数的返回值之和。

climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)
其中 i 定义了当前阶数，而 n 定义了目标阶数。

class Solution {
    public int climbStairs(int n) {
        return climbWays(0, n);
    }
    
    public int climbWays(int curStair, int totalStair){
        if(curStair > totalStair){
            return 0;
        }
        
        if(curStair == totalStair){
            return 1;
        }
        
        return climbWays(curStair +1, totalStair) + climbWays(curStair +2, totalStair);
    }
}

复杂度分析

• 时间复杂度：O(2ⁿ)。树形递归的大小为 2ⁿ。

在 n=5 时的递归树将是这样的：

• 空间复杂度：O(n)。递归树的深度可以达到 n 。

方法 2：记忆化递归

在上一种方法中，我们计算每一步的结果时出现了冗余。另一种思路是，我们可以把每一步的结果存储在 memory 数组之中，每当函数再次被调用，我们就直接从 memory 数组返回结果。

在 memory 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 n 。

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

复杂度分析

• 时间复杂度：O(n) 。树形递归的大小可以达到 n。
• 空间复杂度：O(n) 。递归树的深度可以达到 n。

方法 3：动态规划

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。

第 ii 阶可以由以下两种方法得到：
在第 (i-1) 阶后向上爬 1 阶。
在第 (i-2) 阶后向上爬 2 阶。

所以到达第 i 阶的方法总数就是到第 (i−1) 阶和第 (i−2) 阶的方法数之和。

令 dp[i] 表示能到达第 i 阶的方法总数：
dp[i]=dp[i-1]+dp[i-2]

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

复杂度分析

• 时间复杂度：O(n)，单循环到 n 。
• 空间复杂度：O(n)，dp 数组用了 n 的空间。

方法 4: 斐波那契数

在上述方法中，我们使用 dp 数组，其中 dp[i]=dp[i-1]+dp[i-2]。可以很容易通过分析得出 dp[i] 其实就是第 i 个斐波那契数。

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

现在我们必须找出以 1 和 2 作为第一项和第二项的斐波那契数列中的第 n 个数，也就是说 Fib(1)=1 且 Fib(2)=2。

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

复杂度分析

• 时间复杂度：O(n)。单循环到 n，需要计算第 n 个斐波那契数。
• 空间复杂度：O(1)。使用常量级空间。

方法 5: Binets 方法
算法

这里有一种有趣的解法，它使用矩阵乘法来得到第 nn 个斐波那契数。矩阵形式如下：

令

按照此方法，第 nn 个斐波那契数可以由 Q^n-1[0,0] 给出。

让我们试着证明一下。

我们可以使用数学归纳法来证明这一方法。易知，该矩阵给出了第 3 项（基本情况）的正确结果。由于
这证明基本情况是成立的。

假设此方法适用于查找第 nn 个斐波那契数，即 F_n=Q^n-1[0,0]，那么：

现在，我们需要证明在上述两个条件为真的情况下，该方法可以有效找出第 (n+1) 个斐波那契数，即，F_n+1=Qⁿ[0,0]。

证明：

从而， F_n+1=Qⁿ[0,0]。得证。

我们需要为我们的问题做的唯一改动就是将斐波那契数列的初始项修改为 2 和 1 来代替原来的 1 和 0 。或者，另一种方法是使用相同的初始矩阵 Q 并使用 result = Qⁿ[0,0] 得出最后结果。发生这种情况的原因是我们必须使用原斐波那契数列的第 2 项和第 3 项作为初始项。

public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

复杂度分析

• 时间复杂度：O(log(n))。遍历 log(n) 位。
• 空间复杂度：O(1)。使用常量级空间。

方法 6: 斐波那契公式

我们可以使用这一公式来找出第 n 个斐波那契数：

对于给定的问题，斐波那契序列将会被定义为 F₀ = 1，F₁ = 1，F₂= 2，F_n+2= F_n+1 + F_n。尝试解决这一递归公式的标准方法是设出 F_n ，其形式为 F_n= aⁿ。然后，自然有 F_n+1 = aⁿ⁺¹和 F_n+2= aⁿ⁺²，所以方程可以写作 aⁿ⁺²= aⁿ⁺¹+ aⁿ。如果我们对整个方程进行约分，可以得到 a² = a + 1 或者写成二次方程形式 a² - a- 1= 0。
对二次公式求解，我们得到:

一般解采用以下形式：

n = 0时，有A + B = 1
n = 1时，有

解上述等式，我们得到：

将 AA 和 BB 的这些值带入上述的一般解方程中，可以得到：

public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}

复杂度分析

• 时间复杂度：O(log(n))。pow方法将会用去 log(n) 的时间。
• 空间复杂度：O(1)。使用常量级空间。