爬楼梯
目录摘要解决方案方法 1：暴力法方法 2：记忆化递归方法 3：动态规划方法 4: 斐波那契数方法 5: Binets 方法方法 6: 斐波那契公式摘要假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解决方案方法 1：暴力法算法
在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。而在每一步中我们都会继续调用 \(climbStairs\)这个函数模拟爬 1 阶和 2 阶的情形，并返回两个函数的返回值之和。
\[climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)\]其中 \(i\) 定义了当前阶数，而 \(n\) 定义了目标阶数。
class Solution {public:int climbStairs(int n) {return climb_Stairs(0,n);}int climb_Stairs(int i ,int n){if(i > n)return 0;if(i == n)return 1;return climb_Stairs(i+1,n) + climb_Stairs(i+2,n);}};复杂度分析
时间复杂度：\(O(2^n)\)。树形递归的大小为 \(2^n\) 。
在 \(n=5\) 时的递归树将是这样的：
空间复杂度：\(O(n)\)。递归树的深度可以达到 \(n\) 。
方法 2：记忆化递归算法
在上一种方法中，我们计算每一步的结果时出现了冗余。另一种思路是，我们可以把每一步的结果存储在 \(memo\) 数组之中，每当函数再次被调用，我们就直接从 \(memo\)数组返回结果。
在 \(memo\) 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 \(n\) 。
class Solution {public:int climbStairs(int n) {int memo[n+1];return climb_Stairs(0,n,meno);}int climb_Stairs(int i ,int n,int meno[]){if(i > n)return 0;if(i == n)return 1;if(meno[i] > 0)return meno[i];meno = climb_Stairs(i+1,n,meno) + climb_Stairs(i+2,n,meno);return meno[i];}};复杂度分析
时间复杂度：\(O(n)\)。树形递归的大小可以达到 \(n\)。空间复杂度：\(O(n)\) 。递归树的深度可以达到 \(n\) 。方法 3：动态规划算法
不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
第 ii 阶可以由以下两种方法得到：
在第$ (i-1)$阶后向上爬一阶。在第 \((i-2)\)阶后向上爬 $2 $阶。所以到达第 ii 阶的方法总数就是到第$ (i-1)$ 阶和第 \((i-2)\)阶的方法数之和。
令$ dp[i]$ 表示能到达第 \(i\)阶的方法总数：
\[dp[i]=dp[i-1]+dp[i-2]\]代码：
class Solution {public:int climbStairs(int n) {if(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_n = 1/\sqrt{5}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]\]class Solution {public:int climbStairs(int n) {double sqrt5=sqrt(5);double fibn=pow((1+sqrt5)/2,n+1)-pow((1-sqrt5)/2,n+1);return (int)(fibn/sqrt5);}};