新余做网站公司,深圳十大电商巨头,深圳移动端网站建设模板,个人手机版网站建设假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a;
输入#xff1a;n 2
输出#xff1a;2
解释#xff1a;有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2#…假设你正在爬楼梯。需要 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
方法一 记忆化搜索
class Solution {public int climbStairs(int n) {int[] store new int[n 1];return dfs(n, store);}private int dfs(int i, int[] store){if(i 1){return 1;}if(store[i] ! 0){return store[i];}return store[i] dfs(i - 1, store) dfs(i - 2, store);}
}
方法二递推
class Solution {public int climbStairs(int n) {int[] f new int[n 1];f[0] f[1] 1;//f[2];for(int i 2; i n; i){f[i] f[i - 1] f[i - 2];}return f[n];}
}
方法三空间优化
class Solution {public int climbStairs(int n) {int f0 1;int f1 1;for(int i 2; i n; i){int newF f0 f1;f0 f1;f1 newF;}return f1;}
}
