爬楼梯问题——三种方法（精简版）
爬楼梯问题——三种方法（精简版）
爬楼梯问题是一个经典的算法问题，要求计算从第0级到第n级台阶的不同爬法数量。本文将介绍三种不同的解法：动态规划、矩阵快速幂和通项公式。
方法一：动态规划
思路和算法
用f(x)表示爬到第x级台阶的方案数。最后一步可能跨了一级台阶，也可能跨了两级台阶，所以：
f(x) = f(x-1) + f(x-2)
它意味着爬到第x级台阶的方案数是爬到第x-1级台阶的方案数和爬到第x-2级台阶的方案数的和。很好理解，因为每次只能爬1级或2级，所以f(x)只能从f(x-1)和f(x-2)转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
边界条件
f(0) = 1, f(1) = 1
我们是从第0级开始爬的，所以从第0级爬到第0级我们可以看作只有一种方案，即f(0)=1；从第0级到第1级也只有一种方案，即爬一级，f(1)=1。
这两个作为边界条件就可以继续向后推导出第n级的正确结果。我们不妨写几项来验证一下，根据转移方程得到f(2)=2，f(3)=3，f(4)=5…我们把这些情况都枚举出来，发现计算的结果是正确的。
我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是O(n)的实现，但是由于这里的f(x)只和f(x-1)与f(x-2)有关，所以我们可以用滚动数组思想把空间复杂度优化成O(1)。下面的代码中给出的就是这种实现。
代码
class Solution {
public int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
复杂度分析
时间复杂度：循环执行n次，每次花费常数的时间代价，故渐进时间复杂度为O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为O(1)。
方法二：矩阵快速幂
思路
以上的方法适用于n比较小的情况，在n变大之后，O(n)的时间复杂度会让这个算法看起来有些捉襟见肘。我们可以用「矩阵快速幂」的方法来优化这个过程。
首先构建这样一个递推关系：
[
\left[ \begin{matrix} 1 & 1 \ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} f(n)\ f(n - 1) \end{matrix} \right] = \left[ \begin{matrix} f(n) + f(n - 1)\ f(n) \end{matrix} \right] = \left[ \begin{matrix} f(n + 1)\ f(n) \end{matrix} \right]
]
因此：
[
\left[ \begin{matrix} f(n + 1)\ f(n) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \ 1 & 0 \end{matrix} \right] ^n \left[ \begin{matrix} f(1)\ f(0) \end{matrix} \right]
]
令：
[
M = \left[ \begin{matrix} 1 & 1 \ 1 & 0 \end{matrix} \right]
]
因此我们只要能快速计算矩阵M的n次幂，就可以得到f(n)的值。如果直接求取M^n，时间复杂度是O(n)的，我们可以定义矩阵乘法，然后用快速幂算法来加速这里M^n的求取。
快速幂算法
计算x^n通常需要n次乘法, 时间复杂度为O(n)。
快速幂是通过把nnn转化为二进制来实现的。例如: 计算x^14可以用二进制表示为:
14 = (1110)_2 = 1\times 2^3 + 1\times 2^2 + 1\times 2^1 + 0\times 2^0
那么对应的乘法可以表示为:
x^{14} = x^{2 ^3} \times x^{2^2} \times x^{2 ^1}
格式
def fpowx(x, n):
res = 1
while n:
if n & 1:
res = res * x # 如果计算矩阵，将这里改为矩阵乘法
x = x * x #如果计算矩阵，将这里改为矩阵乘法
n >>= 1 #n右移一位
return res
如何想到使用矩阵快速幂？
- 如果一个问题可与转化为求解一个矩阵的n次方的形式，那么可以用快速幂来加速计算
- 如果一个递归式形如f(n) = \sum_{i = 1}^{m} a_i f(n - i)，即齐次线性递推式，我们就可以把数列的递推关系转化为矩阵的递推关系，即构造出一个矩阵的n次方乘以一个列向量得到一个列向量，这个列向量中包含我们要求的f(n)
A^n \times 列向量 = 列向量
- 一般情况下，形如f(n) = \sum_{i = 1}^{m} a_i f(n-i)可以构造出这样的m \times m的矩阵：第一行为a_i，下面为单位矩阵。
[
\left[ \begin{matrix} a_1 & a_2 & a_3 & \cdots & a_m \ 1 & 0 & 0 & \cdots & 0 \ 0 & 1 & 0 & \cdots & 0 \ 0 & 0 & 1 & \cdots & 0 \ \vdots & \vdots & \vdots & \ddots & \vdots \ 0 & 0 & 0 & \cdots & 1 \ \end{matrix} \right]
]
有些时候我们可以把非齐次线性递推转化为其次线性递推，比如这样一个递推：
f(x) = (2x-6)c + f(x - 1) + f(x - 2) + f(x - 3)
我们可以做这样的变换：
f(x) + xc = [f(x - 1) + (x - 1)c] + [f(x - 2) + (x - 2)c] + [f(x - 3) + (x - 3)c]
令g(x) = f(x) + xc，那么我们又得到了一个齐次线性递：
g(x) = g(x-1) + g(x-2) + g(x-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(logn)。
空间复杂度：O(1)。
方法三：通项公式
思路
之前的方法我们已经讨论了f(n)是齐次线性递推，根据递推方程f(n)=f(n-1)+f(n-2)，我们可以写出这样的特征方程：
x^2 = x + 1
求得x_1 = \frac{1+\sqrt{5}}{2}，x_2 = \frac{1-\sqrt{5}}{2}
设通解为f(n) = c_1 x_1^n + c_2 x_2^n，代入初始条件f(1)=1，f(2)=1
得c_1 = \frac{1}{\sqrt{5}}，c_2 = -\frac{1}{\sqrt{5}}，我们得到了这个递推数列的通项公式：
f(n) = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]
接着我们就可以通过这个公式直接求第n项了。
代码
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方法将会用去O(logn)的时间。
空间复杂度：O(1)。
总结
这里形成的数列正好是斐波那契数列，答案要求的f(n)即是斐波那契数列的第n项（下标从0开始）。我们来总结一下斐波那契数列第n项的求解方法：
- n比较小的时候，可以直接使用过递归法求解，不做任何记忆化操作，时间复杂度是O(2n)，存在很多冗余计算。
- 一般情况下，我们使用「记忆化搜索」或者「迭代」的方法，实现这个转移方程，时间复杂度和空间复杂度都可以做到O(n)。
- 为了优化空间复杂度，我们可以不用保存f(x-2)之前的项，我们只用三个变量来维护f(x)、f(x-1)和f(x-2)，你可以理解成是把「滚动数组思想」应用在了动态规划中，也可以理解成是一种递推，这样把空间复杂度优化到了O(1)。
- 随着n的不断增大O(n)可能已经不能满足我们的需要了，我们可以用「矩阵快速幂」的方法把算法加速到O(logn)。
- 我们也可以把n代入斐波那契数列的通项公式计算结果，但是如果我们用浮点数计算来实现，可能会产生精度误差。