南通网站排名服务,北京百度快速排名,如何修改wordpress权限设置,开发公司进入黑名单后可以销售70. 爬楼梯
难度#xff1a;简单
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a;
输入#xff1a;n 2
输出#xff1a;2
解释#xff1a;有两种方法可以爬到楼…70. 爬楼梯
难度简单
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶示例 2
输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示
1 n 45
个人题解
方法一打表递归优化记忆化递归
思路
分析题目可知首先一定有一种方法就是全是 1。然后逐个将 1 变成 2 插入长度减少 1 的队列中用数学知识可知即从 n-1 中挑 1个 1 变成 2然后下一种即从 n - 2 个 1 中挑 两个 变成 2 。。。依次类推直到全是 2 或者 只有 1 个 1 为止。打表将上述各个结果推出可得当n1,2,3,4,5,6,7,8 时应返回 1,2,3,5,8,13,21,34观察结果规律可得f(n) f(n - 1) f(n -2)则可写出下列代码
class Solution {public int climbStairs(int n) {if (n 1 || n 2) {return n;}return climbStairs(n - 2) climbStairs(n - 1);}
}优化上述代码在 n 越大的时候会重复计算这时可以增加一个容器保存已计算的结果则已计算的结果可以直接返回无需重复计算
class Solution {// 也可以是容量45的数组private static final MapInteger, Integer map new HashMap();public int climbStairs(int n) {if (n 1 || n 2) {return n;}if (!map.containsKey(n)) {map.put(n, climbStairs(n - 2) climbStairs(n - 1));}return map.get(n);}
}时间复杂度O(n) 空间复杂度O(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)转移过来而这里要统计方案总数我们就需要对这两项的贡献求和。
以上是动态规划的转移方程下面我们来讨论边界条件。我们是从第 0 级开始爬的所以从第 0 级爬到第 0 级我们可以看作只有一种方案即 f(0)1从第 0 级到第 1 级也只有一种方案即爬一级f(1)1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下根据转移方程得到 f(2)2f(3)3f(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;}
}复杂度分析
时间复杂度O(n) 空间复杂度O(1)
方法二矩阵快速幂
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)
方法三通项公式
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) Math.round(fibn / sqrt5);}
}作者力扣官方题解 链接https://leetcode.cn/problems/climbing-stairs/solutions/286022/pa-lou-ti-by-leetcode-solution/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
