爬楼梯
目录摘要解决方案方法 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);}};