写点什么

LeetCode 题解:70. 爬楼梯,递归 + 哈希表,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 08 月 01 日

原题链接:https://leetcode-cn.com/problems/climbing-stairs/



该题其实就是求解斐波那契数列,可以参考题解【手绘图解】从递归到动态规划,该题解给出的是动态规划解,下面是递归+哈希表解法。



```javascript []

/**

* @param {number} n

* @return {number}

*/

var climbStairs = function (n) {

// 缓存计算结果

let map = new Map();



const fibonacci = (n) => {

if (n === 1) return 1; // 为1时,直接返回1种走法

if (n === 2) return 2; // 为2时,直接返回2种走法

if (map.get(n)) return map.get(n); // 若已缓存,则返回缓存结果

let result = fibonacci(n - 1) + fibonacci(n - 2); // 其结果为n-1和n-2的结果之和

map.set(n, result); // 设置缓存,下次直接从Map中读取

return result;

};



return fibonacci(n);

};

```



发布于: 2020 年 08 月 01 日阅读数: 49
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:70. 爬楼梯,递归+哈希表,JavaScript,详细注释