题目描述:
假设你正在爬楼梯。需要 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.猜测该题可能涉及的基础操作:目前看不出来。
2.拿特殊的题目尝试一下:
可以发现,第一层台阶非常特殊,虽然题目提供两种操作,但是我们只能爬1步,因此只有1种方案。
3.筛查题目条件:题目仅一个输入,表示有几层台阶。其为我们提供两个操作,一次爬升一楼,或一次爬升两楼。
4.理解:假设我们想爬第n层台阶,要不从n-1层开始爬,要不从n-2层开始爬【除了n=1的情况,题目提供n>=1】
5.猜测:由此可以猜测,想知道第n层台阶有几种爬法,极大可能和n-2,n-1这两层台阶有关。
解题难点1分析:
虽然猜测n层台阶与n-1、n-2可能有关系,但是未证实,其难点,是找到关系内容。
1:如何找到三者的关系?
我们的目标是,找到爬n层的所有方案(虽然只要求给出方案的数目),假设采用穷举法。
假设num【x】表示爬第x层的所有方案数目。(使x>2)【以下的所有数据,默认不超出限制】
当n=x时,x-1到x,是一种方案,x-2到x,也是一种方案。忽略其它,单单最后一步,一共有两种方案。
面对x-1,x-3到x-1可以走2步,x-2到x-1可以走1步。同样是两种方案。
如果爬到x-1和x-2的所有方案num【x-1】和num【x-2】,之间没有重复的序列,就可以证明num【x】=num【x-1】+num【x-2】。
2:如何证明:x-1和x-2,之间一定不存在重复?
对于x-1,1st.如果x-1是从x-3直接跳到x-1,那么掠过x-2,不存在重复。【x-3到达x-2也是一个步骤】
2nd.如果x-1,从x-2爬升到x-1,那么由于x-2到x-1多一步骤,故不重复。
至此证明完毕。
递归代码:
class Solution {
public int climbStairs(int n) {
if(n==1){
return 1;
}
int[] data=new int[n];
data[0]=1;
data[1]=2;
return helper(n-1, data);
}
private int helper(int temp, int[] data){
if(temp==1){
return 2;
}else if(temp==0){
return 1;
}
if(data[temp-1]>0&&data[temp-2]>0){
return data[temp-1]+data[temp-2];
}else if(data[temp-2]>0){
return helper(temp-1, data)+data[temp-2];
}else if(data[temp-1]>0){
return helper(temp-2, data)+data[temp-1];
}
data[temp]=helper(temp-1, data)+helper(temp-2, data);
return data[temp];
}
}
以上内容即我想分享的关于力扣热题8的一些知识。
我是蚊子码农,如有补充,欢迎在评论区留言。个人也是初学者,知识体系可能没有那么完善,希望各位多多指正,谢谢大家。