爬楼梯算法

都知道爬楼梯算法最重要的在于递归的思想，那我们就来聊聊递归

递归是什么？

1. 概念

• 在程序中函数直接或间接调用自己
• 直接调用自己
• 间接调用自己
• 跳出结构,有了跳出才有结果

2. 思想

• 递归的调用,最终还是要转换为自己这个函数
• 如果有个函数fd,如果他是递归函数,到最后问题还是转换为函数fd的形式
• 递归的思想就是将一个未知问题转换为一个已解决的问题来实现

function fd(){
    ...fd()...
}
复制代码

了解了递归之后，我们来聊聊爬楼梯算法

n阶楼梯的走法

首先，当只有一阶楼梯的时候，很显然只有一种走法； 有两阶楼梯的时候，也很显然的知道有两种走法。就会有下面这句判断语句

if (n == 1 || n == 2) {
        return n;
    }
复制代码

一阶二阶的思想就出来了，那如果当阶数是三阶四阶甚至n阶的时候呢? 这个时候递归的思想就出来了，如果阶数是n阶的时候，走法如下：

   climbStairs(n - 2) + climbStairs(n - 1);
复制代码

聊着聊着我们的代码就出来了

var climbStairs = function (n) {
    if (n == 1 || n == 2) {
        return n;
    }
    else {
        return climbStairs(n - 2) + climbStairs(n - 1);
    }
}
复制代码

这个时候就可以开开心心去LeetCode提交代码了，然后你就会发现

???这又是个啥玩意? 我辛辛苦苦打出来的代码，你跟我搞这个？

冷静下来仔细一想，我就发现了问题所在，原来是递归的重复计算导致了内存的溢出，接下来就要优化内存的分配。递归是可以优化成循环的，这里我是用定义多个变量减少内存分配来解决这个问题的。

function climbStairs(n){
    if (n == 1 || n == 2) 
        return n;

let ret = 0,
pre = 2,
prepre = 1;
for(let i = 3; i <= n ;i++){
    ret = pre + prepre;
    prepre = pre;
    pre =ret
}
return ret;
}
复制代码

总结

首先拿到爬楼梯这个问题的时候，我马上就想到了要用递归的方法去做，然后去查询了些关于递归的知识。接着分析问题，楼梯只有一阶二阶的时候是个特殊情况，递归思想写出n阶楼梯时的完整代码，当我去LeetCode提交代码的时候，我又认识到了内存溢出的问题，对代码进行了优化，最后写出了这个代码。