Voyz's Studio.

LeetCode算法笔记--爬楼梯

算法题
字数统计: 188阅读时长: 1 min
2020/07/06 Share

LeetCode算法笔记–Day29

70. 爬楼梯

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例1：
输入: 2
输出: 2

示例2：
输入: 3
输出: 3

我的解答：

1.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for(let i=2;i<n+1;i++){
        dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[n];
};

2.直接用斐波那契数列计算公式

Snip20200706_1.png

1
2
3
4
5
6
7
8
9
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const sqrt_5 = Math.sqrt(5);
    const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
    return Math.round(fib_n / sqrt_5);
};
CATALOG
  1. 1. LeetCode算法笔记–Day29
  2. 2. 70. 爬楼梯
    1. 2.0.0.0.1. 题目：
    2. 2.0.0.0.2. 我的解答：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa