力扣刷题之爬楼梯（7/30）
力扣刷题之爬楼梯
题目如下
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
这道题的要求的话是很清晰的，也就是我们一步楼梯可以有两种走法，就是一次一层还有就是一次两层。上一层的当然只有一种，然后上两层的话有两种，就是一步一步，或者一次性走两层。上三层的话的方法就是走一层和走两层的方法的和。这个只体现的方法的数量上。
第n个层可以从n-1一步到达，也可以从n-2采用两种方法到达。 所以呢!可以列出一个方法的函数表达式 f（n）= f(n-1)+f(n-2)。这样就确定了一个递推的公式,我们可以递归去计算，但是要考虑递归的出口，当n等于2的时候需要去直接给定一个值为2，因为计算f(0)是不合理的，所以我们这样去考虑了。
我们可以首先这样去做，是这样的一个逻辑
package leetcode;
/**
* @author 兰舟千帆
* @version 1.0
* @date 2022/7/30 9:37
*/
public class CommonFactor {
public static void main(String[] args) {
int n = 10;
function_count(n);
}
public static int function_count(int n)
{
if (n==1||n==2)
{
return n;
}
return function_count(n-1)+function_count(n-2);
}
}但是放在力扣的话，运行的话。
这样的话，力扣这里测试的话，就狐疑超出时间的限制。因为递归是比较消耗时间的。
其实可以思考一下，我们的递归简单的有没有去优化的方法，可以这样去思考一个问题，比如我们计算从第一层到第五层的方法数，我们需要在递归里面用f（4）+f(3)，然后这两层就一直递归到借宿条件，所以这里存在重复的计算
f(4)=f(3)+f(2)
f(3)=f(2)+f(1)对于这里我们可以这样去想，如果f(4)中通已经递归计算出f(3)，那么我们就就没有必要再去计算f(3)了，我们直接去用已经计算出的这个结果不就行了？为什么还有去算呢？我们这样去优化，众所周知，HashMap不允许重复的键。
于是呢，我们可以这样去写
class Solution {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
public int climbStairs(int n) {
if(n==1||n==2)
{
return n;
}
else if(null!=map.get(n)){
return map.get(n);
}else{
int result = climbStairs(n-1)+climbStairs(n-2);
map.put(n,result);
return result;
}
}
}这样优化的递归毫不逊色。
上面这两种方法的话，本质上还是递归。递归的话，你可以去想象为一颗树，我们从树的根乡下对孩子和叶子进行遍历处理，最后再返回结果。这是一种至顶向下的方法。
我们可以采用至底向上累加的方法
class Solution {
public int climbStairs(int n) {
// Map<Integer,Integer> map = new HashMap<Integer,Integer>();
// if(n==1||n==2)
// {
// return n;
// }
// else if(null!=map.get(n)){
// return map.get(n);
// }else{
// int result = climbStairs(n-1)+climbStairs(n-2);
// map.put(n,result);
// return result;
// }
int result =0;
int n1 =2;
int n2 =1;
if (n==1||n==2)
{
return n;
}
for(int i=3;i<=n;i++)
{
result = n1+n2;
n2 = n1;
n1 = result;
}
return result;
}
}其实它很类似于反向的递归，但是这种方法比递归还好理解，非常的巧妙。 其实就类似于这样的树。最底部的就是1,2，然后依次累计上去，同时for循环里面存在一个复制和交换，这样就可以认为在B已经累加出来后，同时又指定了c,但是c的值我们已经计算出来了，就是上一个result返回的结果。依次类推。
但是力扣的解题大神总是出乎意料的牛逼，不过在牛逼的基础上其实还是懂得更多。
然后他就一直计算下去了，我打赌，他之前的方法一定是超时了，所以才这样去超出三界的方式去解题了。秀。