070. 爬楼梯

题目描述:

难度：Easy

相关话题：动态规划

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意： 给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

---

思路：

DP，dp[i]表示当前楼梯有几种走法，dp[i]=dp[i-1]+dp[i-2]。

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  // let mem=[]
  // function getSteps(n){
  //     if(mem[n])return mem[n]
  //     if(n===1)return 1
  //     if(n===2)return 2
  //     let steps=getSteps(n-1)+getSteps(n-2)
  //     mem[n]=steps
  //     return steps
  // }
  // return getSteps(n)
  let dp=Array(n).fill(0)
  dp[0]=1
  dp[1]=2
  for(let i=2;i<n;i++){
    dp[i]=dp[i-1]+dp[i-2]
  }
  return dp[n-1]
};

更多题解可以访问我的 码农周刊 仓库：https://github.com/meibin08/free-programming-books， 一起学习更多前端前沿知识。