day143-LeetCode 70. Climbing Stairs

题目

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

分析

这种从无穷之中找规律的题目,难免会想到动态规划,所以可以先分情况来~

n为阶梯数,p表示方法种类
n = 1; p = 1
n = 2; p = 1+1
n = 3; p = 1+2
n = 4; p = 3+2
规律,斐波那契数列f(n) = f(n-1) + f(n-2)

题解

function climbStairs (n) {
if (n <= 1) return 1
let prev = 1
let cur = 1
// f(n) = f(n -1) + f(n -2)
for (let i = 2; i <= n; i++) {
let temp = cur
cur = cur + prev
prev = temp
}
return cur
}
文章作者: lmislm
文章链接: http://lmislm.com/2019/06/04/2019-06-04/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LMISLMのBlog