题目

动态规划

因为爬楼梯的最后一步必然是 1 或 2 ，因此就有了递推公式：$f(x)=f(x-1)+f(x-2)$

class Solution {
public:int climbStairs(int n) {int f1 = 0, f2 = 1;for(int i = 1; i <= n; ++i) {f1 = f1 + f2;swap(f1, f2);}return f2;}
};

矩阵快速幂

当 n 很大时，上述的递推式可以改写成矩阵的形式：
$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]=\left[\begin{array}{c}f(n)+f(n-1)\\ f(n)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$
因此：
$$\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}f(1)\\ f(0)\end{array}\right]$$
得到了矩阵的公式，就可以使用快速幂的方法来加速。

用向量处理矩阵，代码如下：

class Solution {
public:vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {vector<vector<long long>> c(2, vector<long long>(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;}vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {vector<vector<long long>> ret = {{1, 0}, {0, 1}};while (n > 0) {if ((n & 1) == 1) {ret = multiply(ret, a);}n >>= 1;a = multiply(a, a);}return ret;}int climbStairs(int n) {vector<vector<long long>> ret = {{1, 1}, {1, 0}};vector<vector<long long>> res = matrixPow(ret, n);return res[0][0];}
};