首页 > 试题广场 >

爬楼梯

[编程题]爬楼梯
  • 热度指数:17643 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
在你面前有一个n阶的楼梯,你一步只能上1阶或2阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯。

输入描述:
一个正整数n(n<=100),表示这个楼梯一共有多少阶


输出描述:
一个正整数,表示有多少种不同的方式爬完这个楼梯
示例1

输入

5

输出

8
写一个c语言比较简洁的大整数加法
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> dp(n + 5, vector<int> (100, 0));
    dp[1][0] = 1;
    dp[2][0] = 2;
    int len = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 0; j < len; j++) {
            dp[i][j] += dp[i - 1][j] + dp[i - 2][j];
            if (dp[i][j] > 9) {
                dp[i][j + 1] += dp[i][j] / 10;
                dp[i][j] %= 10;
                len += (j == len - 1);
            }
        }
    }
    for (int i = 0; i < len; i++) cout << dp[n][len - i - 1];
    cout << endl;
    return 0;
}


编辑于 2020-03-11 19:45:54 回复(2)
首先这个题目的模型是斐波那契数列(参考剑指offer的青蛙跳台阶),思路是很清晰的,但是有一个很棘手的问题:这个题C++没有大整数类,而题目的用例太大了,long long也只能通过55%的用例,所以只能通过字符串来显示。所以整道题的重点就是如何进行字符串相加,手写字符串相加函数、
下面的注释很详细了,可以参考
#include <iostream>
#include <string>
using namespace std;

string BigData(string s1, string s2){
    string res = "";
    int i = s1.size() - 1;
    int j = s2.size() - 1;
    int carry = 0;  //进位
    while (i >= 0 || j >= 0){
        // s2一定大于s1(斐波那契数列的后者 > 前者)
        if(i < 0){
            //当小的字符串先走完时,就剩大字符串了,同理进行逐位添加
            res = to_string((s2[j] - '0') + carry) + res;
            carry = 0;  //只剩一个字符串就不存在进位了,因为都是个位数
        } else{
            //从后往前进行逐位相加,如123+567,从3+7开始往前加,别忘了加上进位
            int tmp = (s1[i] - '0') + (s2[j] - '0') + carry;
            carry = tmp / 10;  //得到进位
            tmp = tmp % 10;    //得到余数
            res = to_string(tmp) + res; //这里顺序记得不能颠倒,不然就错了
        }
        --i; --j;
    }
    //为什么下面还要判定呢?因为比如3+7应该等于10,但是
    //上面的计算出的res只有0(余数),所以这里要考虑周全
    if(carry == 1)
        res = '1' + res;
    return res;
}
int main(){
    int n;
    cin >> n;
    //斐波那契
    if(n == 1){
        cout << 1 << endl;
        return 0;
    } else if(n == 2){
        cout << 2 << endl;
        return 0;
    }
    string i = "1";
    string j = "2";
    string ans = "";
    for(int k = 1; k <= n - 2; ++k){
        ans = BigData(i, j);  // i + j
        i = j;   
        j = ans;
    }
    cout << ans << endl;
    return 0;
}


编辑于 2020-06-03 21:22:49 回复(0)
递推公式很简单,f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=2.
值得注意的是本题还有大整数问题,所以使用转化为字符串形式,额外写一个大整数相加函数
#include<iostream>
using namespace std;
//大整数相加函数
string add(string a,string b)
{
    int i=a.size()-1;
    int j=b.size()-1;
    string res="";
    int carry=0;
    while(i>=0&&j>=0)
    {
        char tmp;
        int num;
        num=(a[i]-48)+(b[j]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        i--;
        j--;
    }
    while(i>=0)
    {
        char tmp;
        int num;
        num=(a[i]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        i--;
    }
    while(j>=0)
    {
        char tmp;
        int num;
        num=(b[j]-48)+carry;
        carry=num/10;
        num=num%10;
        tmp=char(num+48);
        res=tmp+res;
        j--;
    }
    if(carry>0)
    {
        res=char(carry+48)+res;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    string a[n+1];
    for(int i=0;i<n+1;i++)
    {
        a[i]='0';
    }
    a[0]='1';
    a[1]='1';
    for(int i=2;i<n+1;i++)
    {
        a[i]=add(a[i-1],a[i-2]);
    }
    cout<<a[n];
}

发表于 2019-10-28 12:14:22 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int num[103][30] = {0};
    num[1][29] = 1;//第一项
    num[2][29] = 2;//第二项 
    for (int i = 3; i <= n; i++)
    {
        for (int j = 29; j >= 0; j--)//循环,数组行是从1开始,列是从0开始
        {
            if ((num[i - 1][j] + num[i - 2][j]+num[i][j]) >= 10)//进位,占多一个元素
                num[i][j - 1] += 1;
            num[i][j] = (num[i - 1][j] + num[i - 2][j] + num[i][j]) % 10;
        }
    }
    int j = 0;
    while (num[n][j] == 0)
        j++;
    for (int i = j; i < 30; i++)
        cout << num[n][i];
    return 0;
}

发表于 2019-07-03 22:07:12 回复(2)
import sys
def diffroad(n):
    res =[1,2]
    if n<3:
        return res[n-1]
    for i in range(3,n+1):
        res[(i-1)%2] += res[i%2]
    return res[(i-1)%2]
    
if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    print(diffroad(n))

发表于 2019-09-07 22:41:08 回复(0)
import java.util.*;
import java.math.*;
public class Main{
    static BigInteger func(int n){
        if(n==0)
            return new BigInteger("0");
        if(n==1)
            return new BigInteger("1");
        BigInteger[] ll=new BigInteger[n];
        ll[0]=new BigInteger("1");
        ll[1]=new BigInteger("2");
        for(int i=2;i<n;i++){
            ll[i]=ll[i-1].add(ll[i-2]);
        }
        return ll[n-1];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(func(n));
    }
}

发表于 2020-08-25 00:09:06 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[101][30] = {0};
    a[1][29] = 1;
    a[2][29] = 2;
    for(int i=3;i<=n;i++)
        for(int j=29;j>=0;j--){
            int t = a[i-1][j]+a[i-2][j]+a[i][j];
            if(t >= 10)
                a[i][j-1] += 1;
            a[i][j] = t%10;
        }
    bool zero = true;
    for(int j=0;j<30;j++){
        if(zero && a[n][j]!=0)
            zero = false;
        if(!zero)
            cout<<a[n][j];
    }
    cout<<endl;
    return 0;
}

发表于 2019-12-30 00:56:26 回复(1)

这里有一个超大数,CPP会溢出。直接用递归 cpp会超时,引入滚动数组,从低位开始计算,避免重复运算

if __name__ == "__main__":
    n = int(input().strip())
    dp = [1,2,0]
    if n<=2:
        print(n)
    else:
        for i in range(3, n+1):
            dp[-1]= dp[0]+dp[1]
            dp[0] = dp[1]
            dp[1]=dp[2]
        print(dp[2])

发表于 2019-07-22 11:05:42 回复(0)

考察斐波那契数列
题目要求:只能跳1阶或者2阶。
定义阶有种跳法

  1. 假定第一次跳的是一阶,那么剩下的是 n-1 个台阶,跳法是;
  2. 假定第一次跳的是2阶,那么剩下的是 n-2 个台阶,跳法是
  3. 总跳法为:
  4. .

初次提交这个题会发现通过率只有 50%,是因为没有考虑到整数溢出的问题,用BigInteger处理就Ok了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        if (n < 3) {
            System.out.println(n);
            return;
        }
        BigInteger one = BigInteger.valueOf(1);
        BigInteger two = BigInteger.valueOf(2);
        BigInteger ret = BigInteger.valueOf(0);

        for (int i = 3; i <= n; i++) {
            ret = one.add(two);
            one = two;
            two = ret;
        }
        System.out.println(ret);
    }
}
发表于 2019-07-28 13:59:23 回复(2)
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<BigInteger> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            BigInteger temp = (i <= 2) ? BigInteger.valueOf(i) : list.get(i - 2).add(list.get(i - 3));
            list.add(temp);
        }
        System.out.println(list.get(list.size() - 1));
    }
}
发表于 2019-07-08 16:16:43 回复(0)
""""
台阶问题,考虑动态规划
设dp[n]为n阶台阶的方法数,
每次只能上1、2阶台阶,要想到达n,则只能由n-1,n-2到达
dp[n] = dp[n-1] + dp[n-2]
边界 dp[0] = dp[1] = 1
"""

if __name__ == "__main__":
    n = int(input().strip())
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n])

发表于 2019-07-13 14:54:55 回复(1)
这道题不考虑大数相加的话是这样的思路,和斐波拉一样
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = Number(line)
        let dp = new Array(num+1).fill(0)
        dp[1] = 1
        dp[2] = 2
        for(let i = 3; i <= num; i++) {
            dp[i] = dp[i-1] + dp[i-2]
        }
        console.log(dp[num])
    }
}()
但是这道题,必须得考虑大数相加
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = Number(line)
        let dp = new Array(num+1).fill(0)
        dp[1] = 1
        dp[2] = 2
        for(let i = 3; i <= num; i++) {
            dp[i] = numAdd(dp[i-1].toString(), dp[i-2].toString())
        }
        console.log(dp[num])
    }
    /**
     * 这个函数是用来进行大数相加的,可以反复阅读一下
     */
    function numAdd(first, second) {
        // 取两个数字的最大长度
        let maxLength = Math.max(first.length, second.length);
        // 用 0 去补齐长度
        first = first.padStart(maxLength , 0);
        second = second.padStart(maxLength , 0); 
        // 定义加法过程中需要用到的变量
        let temp = 0;
        let carry = 0;   // "进位"
        let sum = "";
        for(let i = maxLength-1; i >= 0; i--){
            temp = parseInt(first[i]) + parseInt(second[i]) + carry;
            carry = Math.floor(temp / 10);
            sum = temp % 10 + sum;
        }
        if(carry == 1){
            sum = "1" + sum;
        }
        return sum;
    }
}()
发表于 2023-04-16 21:01:07 回复(0)
import java.math.BigDecimal;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sum = in.nextInt();
        if (sum == 1) {
            System.out.println(1);
            return;
        } else if (sum == 2) {
            System.out.println(2);
            return;
        } else if (sum <= 0) {
            System.out.println();
            return;
        }
        BigDecimal[] ary = new BigDecimal[sum];
        ary[0] = BigDecimal.valueOf(1);
        ary[1] = BigDecimal.valueOf(2);
        for (int i = 2; i < sum; i++) {
            ary[i] = ary[i - 2].add(ary[i - 1]);
        }
        System.out.println(ary[sum - 1].toString());
    }
}


发表于 2023-02-17 15:56:49 回复(0)
这题python倒在了内存上
前面的大佬的方法也不好使,.我这边加了字典缓存一下可以了
n = int(input())

cache = dict()

def foo(x):
    if x in cache:
        return cache[x]
    if x == 1:
        return 1
    elif x == 2:
        return 2
    res = foo(x - 1) + foo(x - 2)
    cache[x] = res
    return res


print(foo(n))


发表于 2023-02-11 20:40:08 回复(0)
需要自己找到上楼梯次数的规律
阶梯:1,2,3,4,5,6,
需要的次数:1,2,3,5,8,13
规律为第n梯需要的步数为(n-1)梯的步数加上(n-2)梯的步数
另外,改题会验证大量的步数,对内存要求特别高,需要导入了一个lru_cache
import sys
from functools import lru_cache
@lru_cache
def work(n):
    if n ==1 or n == 2:
        return n
    else:
        return work(n-1) + work(n-2)
for line in sys.stdin:
    a = line.strip("\r\n")
    res = work(int(a))
    print(res)

发表于 2022-11-26 19:20:07 回复(0)
#include <bits/stdc++.h>
using namespace std;

string strAdd(string a, string b) {
    int level = 0;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int aIndex = 0;
    int bIndex = 0;
    string res = "";
    while (aIndex < a.size() || bIndex < b.size() || level != 0) {
        int val = (aIndex < a.size() ? a[aIndex++] - '0' : 0) + (bIndex < b.size() ? b[bIndex++] - '0' : 0) + level;
        level = val / 10;
        res += to_string(val % 10);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<string> dp(101, "0");
    dp[1] = "1";
    dp[2] = "2";
    for (int i = 3; i < 101; i++) {
        dp[i] = strAdd(dp[i - 1], dp[i - 2]);
    }
    cout << dp[n] << endl;
    return 0;
}

发表于 2022-07-31 14:54:10 回复(0)
本题结果用long类型存放也会超出范围,只能使用字符串存放。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] dp = new String[101]; // 楼梯的台阶数小于等于100
        dp[1] = String.valueOf(1);
        dp[2] = String.valueOf(2);
        for (int i = 3; i <= 100; i++) {
            dp[i] = add(dp[i - 1], dp[i - 2]); // 两个字符串相加
        }

        int n = sc.nextInt();
        System.out.println(dp[n]);
    }

    public static String add(String s1, String s2) {
        int n1 = s1.length() - 1;
        int n2 = s2.length() - 1;
        int add = 0; // 记录进位
        StringBuffer sb = new StringBuffer(); // 存放结果
        while (n1 >= 0 || n2 >= 0) {
            int x = (n1 >= 0) ? s1.charAt(n1) - '0' : 0;
            int y = (n2 >= 0) ? s2.charAt(n2) - '0' : 0;
            int sum = x + y + add;
            if (sum > 9) {
                sb.insert(0, sum % 10);
                add = 1;
            } else {
                sb.insert(0, sum);
                add = 0;
            }
            n1--;
            n2--;
        }
        if (add == 1) sb.insert(0, 1); // 最后查看是否有进位
        return sb.toString();
    }
}


发表于 2021-09-09 21:45:39 回复(0)
import java.util.*;
import java.math.BigInteger;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        BigInteger[] a = new BigInteger[n+1];
        if(n<3) System.out.println(n);
        if(n>=3){
            a[1]=new BigInteger("1");
            a[2]=new BigInteger("2");
            for(int i = 3;i<=n;i++){
                a[i]=a[i-1].add(a[i-2]);
                }
            System.out.println(a[n]);
        }
    }
}
发表于 2021-09-07 20:52:59 回复(0)
n=int(input())
a,b = 1,1
for _ in range(n):
    a,b=b,a+b
print(a)    

发表于 2021-03-31 20:33:51 回复(0)
package newcoder;

import java.math.BigInteger;// 这个有大整数问题,long也不行,只能采用BigInteger。其实也可以用字符串按位置相加,但是得额外写程序。
import java.util.Scanner;
import java.util.function.BiConsumer;

public class 小米爬楼梯 {
    static BigInteger JumpFloor(int number) {

        if(number == 0) return new BigInteger(String.valueOf(0));
        // 注意,这里的number == 1和number == 2都要写上,是因为下面已经用到了number[1]和number[2]
        if(number == 1) return new BigInteger(String.valueOf(1));
        if(number == 2) return new BigInteger(String.valueOf(2));
        BigInteger[] times = new BigInteger[number+1];
        times[0] = new BigInteger(String.valueOf(0));//第0级台阶
        times[1] = new BigInteger(String.valueOf(1));
        times[2] = new BigInteger(String.valueOf(2));
        for (int i = 3; i < times.length; i++) {
            times[i] = times[i-1] .add(times[i-2]);// 注意大整数相加是调用方法相加的,不是直接用+号的。
        }
        return times[number];
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        System.out.println(JumpFloor(number));// 竟然大整数的输出是和普通整数一样的,可以直接println。
    }
}

发表于 2020-05-20 20:53:56 回复(0)