首页 > 试题广场 >

上楼梯

[编程题]上楼梯
  • 热度指数：1143 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有n级台阶，每一步可以走1级或2级，问一共有多少种走法

输入描述:
台阶的级数n


输出描述:
走法数量
示例1

输入

2

输出

2

说明

走法为1+1或2
示例2

输入

3

输出

3

说明

走法为1+1+1或1+2或2+1
算法知识视频讲解
添加回答
牛客570032122号头像 牛客570032122号 
function getCount(n) {
  let count = 1
  for (let i = n - 1; i >= 1; i--) {
    if (i * 2 < n) {
      return count
    }
    if (i * 2 === n) {
      return count += 1
    }
    count += i
  }
  return count
}


发表于 2020-05-20 19:23:23 回复(0)
玖燃头像 玖燃

就是一道斐波那契数列的经典问题，学习算法基础递归的时候老师都有讲。

while (line = readline()) {
    var n = parseInt(line);
    var res = fibonacci(n);
    print(res);
}

function fibonacci(n) {
    // 递归基
    if (n <= 1) {
        return 1;
    }

    // 递归计算实例
    return fibonacci(n - 1) + fibonacci(n - 2);
}
发表于 2019-11-26 20:04:57 回复(0)
桃枝头像 桃枝 
function gg(num){
    if(num<=0){return 0;}
    if(num == 1){return 1;}
    if(num == 2){return 2;}
    return gg(num-1)+gg(num-2)
}

发表于 2019-11-25 10:11:16 回复(0)
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:bilibili📺-上楼梯（经典递归）
leetcode 70 climbstairs 
//leetcode 70 climbStairs 
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        let n = +inArr[0]
        console.log(climbStairs(n))
    }
})
var climbStairs = function(n) {
    if(n<3)return n
    let f1=1, f2 =2 ,f, i=3
    while(i++<=n){
        f=f1+f2
        f1=f2
        f2=f
    }
    return f

};
发表于 2020-02-27 10:51:07 回复(0)
向上仰望头像 向上仰望
看到前边大佬的答题，wc，这不是斐波那契数列嘛。
这里我贴个改进的方法。前边有大佬用了递归，还有 用数组进行改进的。我这边再改进一下
利用辗转相加法的原理，不用数组也能计算结果
function fib2(n){
    if (n<=0){return 0}
    if (n===1){return 1}
    if(n===2){return 2}
    s1=1
    s2=2
    for (let i=2;i<n;i++){
        s2=s1+s2
        s1=s2-s1
    }
    return s2;
}
原因: 数组的缺点，每次到第4,5,6...项的时候，前边的1,2，3..项就不需要了。造成空间浪费。而我们最终的目标是取得第n个斐波那契数
而且每次计算下一项的值，都是利用上一次循环的 s1，s2的值，所以可以这样优化
发表于 2021-08-24 17:24:03 回复(0)
某不知名用户头像 某不知名用户
function fibonacci(n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

发表于 2020-07-01 00:23:07 回复(0)
奕※時＾毀￠头像 奕※時＾毀￠
import java.util.Scanner;
public class Main{
    public static void main(String[] args) { 
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        System.out.println(cal(n));
        scanner.close();
    }
    public static int cal(int n) {
        if(n<0)  //不符合情况
            return 0;
        if(n==0)
            return 1;
        return cal(n-1)+cal(n-2);
    }
}

发表于 2020-03-23 12:35:23 回复(0)
JavaScript
persele头像 persele
使用数组保存变量。比使用递归节省时间。。。 
    function NumberOf1(number) {
      // write code here
      var arr = [1, 2]
      for (var i = 2; i < number; i++) {
        arr[i] = arr[i - 1] + arr[i - 2]
      }
      return arr[number - 1]
    }


发表于 2020-02-10 12:14:59 回复(1)
AllWeKnow头像 AllWeKnow
共n个楼梯，第一次跳1阶，后面还有n-1，有n-1种跳法；第一次跳两个台阶，后面还有n-2，有n-2种跳法。所以递归方式是f(n-1)+f(n-2) 
function getStairs(stair) {
    if(stair <= 0) {
        return0
    }
    if(stair === 1) {
        return1
    }
    if(stair === 2) {
        return2
    }
 
    return getStairs(stair - 1) + getStairs(stair - 2)
}
 
conststair = parseInt(readline())
console.log(getStairs(stair))


编辑于 2020-07-02 11:10:40 回复(0)
福禄小金刚头像 福禄小金刚 
// 时间复杂度O(N)，空间复杂度O(1)
function climbingWays(n) { // 爬到n阶楼梯的方法个数

  // 假设楼梯一次只能爬一级或者两级
  
  if(n < 1) {
    return 0;
  }

  if(n == 1) {
    return 1;
  }

  if(n == 2) {
    return 2;
  }

  // 由于爬楼梯阶层只需要前两级阶层的个数，只需保存两个数就可以
  var a = 1;
  var b = 2;
  var temp = 0;

  for(var i = 3; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }

  return temp;

}
  
const stair = parseInt(readline())
console.log(climbingWays(stair))

发表于 2020-11-19 03:06:42 回复(0)
多喝开开头像 多喝开开 
const n = parseInt(readline());

const test = (nums) => {
    let arr = [1, 2];
    for (let i = 2; i <= nums; i++) {
        arr[i] = arr[i - 2] + arr[i - 1];
    }
    return arr[nums - 1]
}
let res = test(n);
console.log(res);
爬楼梯问题
发表于 2020-10-17 20:29:43 回复(0)
BlessingSoftware头像 BlessingSoftware 
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  const memo = []
  memo[1] = 1
  memo[2] = 2
  for (let i =3; i <= n; i++) {
    memo[i] = memo[i - 2] + memo[i - 1]
  }

  return memo[n]
};

发表于 2020-08-03 16:27:29 回复(0)
nyz123头像 nyz123
我这有啥问题呀 
var climbStairs = function(n) {
    if(n==1) return 1;
    else if(n==2) return 2;
    return climbStairs(n-1)+climbStairs(n-2)
};

发表于 2020-02-28 01:02:58 回复(0)
EuphoriaCHN头像 EuphoriaCHN
只求第N项，递归容易爆栈，数组容易超内存，只用两个游标去维护就好（原谅我用C++） 
if (n == 1) {
    cout << 1;
    return 0;
}

long before = 1, after = 2;

for (int i = 3; i <= n; i++) {
    long temp = before + after;
    before = after;
    after = temp;
}

cout << after;

发表于 2020-02-14 21:51:04 回复(0)
千叶风行者头像 千叶风行者 
function main(n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    let left = 1;
    let right = 2;
    let sum = 0;
    for(let i = 3 ; i <= n ; i++) {
        sum = left + right;
        left = right;
        right = sum;
    }
    return sum;
}

while (line = readline()) {
    var n = parseInt(line);
    var res = main(n);
    print(res);
}
1.动态规划
2. 空间复杂度 :O(1)
发表于 2020-02-05 02:50:12 回复(0)
nactran头像 nactran
动态规划。
设k[i]代表爬到第i层的总解法数。从第三层开始的每一层可以从第 i- 1 层迈一步到达，或者从第 i - 2层迈两步到达，所以解法数k[i] = k[i-1] + k[i-2] （i>2) 
此外考虑 k[1] = 1, k[2] = 2 
#include<iostream>
using namespace std;
 
int main()
{
    int n;
    scanf("%d",&n);
    int k[n+1];
    k[0] = 1;
    k[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        k[i] = k[i-1] + k[i-2];
    }
    printf("%d",k[n]);
    return 0;
}


发表于 2019-11-29 16:44:00 回复(0)
提交观点

问题信息

前端工程师 哔哩哔哩 2020
上传者：小小
难度：
16条回答 2463浏览

热门推荐

通过挑战的用户

相关试题

上楼梯

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号