爬楼梯算法

我们都知道爬楼梯算法最重要的就是递归的思想，那么我们就来说说递归，什么是♿递归？

1. 概念

• 程序中，函数直接或间接调用自身
• 直接调用自身
• 间接调用自身
• 跳出结构体，跳出才有结果 思考
• 递归调用，最后还是要转换成自己的函数
• 如果有函数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提交代码的时候，我意识到了内存溢出的问题，并对代码做了一些修改。优化了一下，终于写出了这段代码。

作者：梦想的天空异常蓝
链接：https://juejin.im/post/5e971dc1e51d45470246073b
来源：掘金归作者所有。商业转载请联系作者获取授权。非商业转载请注明出处。