首页 > 试题广场 >

爬楼梯2

[编程题]爬楼梯2
  • 热度指数：6472 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
在你面前有一个n阶的楼梯(n>=100且n<500)，你一步只能上1阶或3阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯（到最后一层为爬完）。
(注意超大数据)

输入描述:
一个正整数，表示这个楼梯一共有多少阶


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

输入

100

输出

24382819596721629

备注:
注意时间限制
算法知识视频讲解
添加回答
Python
卷积神经网络哦头像 卷积神经网络哦
python的int型无限大(只要内存够) 因此这种题python是最好的选择
简单的动态规划 
arr = [0 for i in range(int(input()) + 1)]
arr[0], arr[1], arr[2] = 1, 1, 1
for i in range(3, len(arr)):
    arr[i] = arr[i-1] + arr[i-3]
print(arr[-1])


发表于 2019-12-26 11:59:29 回复(0)
freezerhan头像 freezerhan
矩阵快速幂 
def matmul(A, B):
    C = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][j] += (A[i][k] * B[k][j])
    return C

def mat_power(A, count):
    B = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    while (count > 0) :
        if count % 2 == 1:
            B = matmul(B, A)
        A = matmul(A, A)
        count //= 2
    return B

def work():
    n = int(input())
    f = [0 for i in range(n + 1)]
    f[0] = f[1] = f[2] = 1
    f[3] = 2
    if n <= 3:
        print(f[n])
        return
    A = [[f[2], f[0], f[1]], [f[3], f[1], f[2]], [0, 0, 0]]
    B = [[1, 0, 1], [1, 0, 0], [0, 1, 0]]
    count = n - 2 - n % 2
    B = mat_power(B, count)
    B = matmul(A, B)
    if n % 2 == 1:
        print(B[1][0])
    else:
        print(B[0][0])
work()


发表于 2019-11-02 14:13:18 回复(0)
Java
谁的电脑头像 谁的电脑 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        BigInteger[] count = new BigInteger[n];
        count[0] = new BigInteger("1");
        count[1] = new BigInteger("1");
        count[2] = new BigInteger("2");
        for (int i = 3; i < n; i++) {
            count[i] = count[i - 1].add(count[i - 3]);
        }
        System.out.println(count[n - 1]);
    }
}
编辑于 2019-07-15 17:02:40 回复(4)
C++
牛客409434554号头像 牛客409434554号 
#include<bits/stdc++.h>
using namespace std;
string jiafa(string a,string b)
{
    int cdc=a.length()-b.length(),jw=0;
    string ans;ans.resize(cdc>0?a.length():b.length());
    if(cdc>=0)    for(int i=0;i<cdc;i++)    b='0'+b;
    else    for(int i=0;i>cdc;i--)    a='0'+a;
    for(int i=a.length()-1;i>=0;i--) {
        int m=a[i]-'0'+b[i]-'0'+jw;
        jw=m/10;
        ans[i]=m%10+'0';
    }
    if(jw)    ans='1'+ans;
    return ans;
    
}
int main()
{
    int n;cin>>n;
    string f[500]={"1","1","1","2"};
    for(int i=4;i<=n;i++)    f[i]=jiafa(f[i-1],f[i-3]);
    cout<<f[n]<<endl;
}
愚蠢的我在做的时候还想，这题帖个动归标签是不是太糊弄了，其实是考大数运算的吧，结果看到PYTHON开挂的兄弟，还是怪我会的太少。。。
发表于 2022-04-06 22:47:49 回复(0)
pein531头像 pein531
动态规划，当前阶梯可能是前一阶跨上来的，也可能是前三阶跨上来的 
n = int(input())
steps = [0]*(n + 1)
# 楼梯阶数小于等于2的时候只有一种爬法（一次爬一阶），阶数为3的时候有两种爬法（一次爬一阶或直接上三阶）
steps[1], steps[2], steps[3] = 1, 1, 2
for i in range(4, n + 1):
    steps[i] = steps[i - 1] + steps[i - 3]    # 可能是前1阶爬上来的，也可能是前3阶爬上来的
print(steps[-1])


发表于 2021-02-27 14:55:12 回复(0)
给我offer我要offer头像 给我offer我要offer 
import java.util.*;
import java.math.*;
public class Main{
    static BigInteger func(int n){
        BigInteger[] ll=new BigInteger[n+1];
        ll[1]=new BigInteger("1");
        ll[2]=new BigInteger("1");
        ll[3]=new BigInteger("2");
        for(int i=4;i<=n;i++){
            ll[i]=ll[i-1].add(ll[i-3]);
        }
        return ll[n];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(func(n));
    }
}

发表于 2020-08-24 23:33:44 回复(0)
louis_ncu头像 louis_ncu 
/*
*参考大佬的代码写的，在此处感谢 @夏夜飘雪
* 链接：https://www.nowcoder.com/questionTerminal/b178fcef3ed4448c99d7c0297312212d?f=discussion
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<vector<int>> dp(n+1, vector<int>(100, 0));
    int len = 1;
    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[3][0] = 2;
    for(int i=4; i<=n; i++) {
        for(int j=0; j<len; j++) {
            dp[i][j] += dp[i-1][j] + dp[i-3][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 -1 -i];
    }
    cout<<endl;
    return 0;
}
编辑于 2020-05-10 00:14:40 回复(0)
gywy头像 gywy

DP + 高精度做法 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 510;
vector<int> dp[N];
int n;


vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i ++)
    {
      if (i < a.size()) t += a[i];
      if (i < b.size()) t += b[i];
      c.push_back(t % 10);
      t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}

int main()
{
    cin >> n;
    dp[0] = vector<int> (1, 1);
    for (int i = 1; i <= n; i ++)
    {
        dp[i] = dp[i - 1];
        if (i >= 3) dp[i] = add(dp[i], dp[i - 3]);
    }
    for (int i = dp[n].size() - 1; i >= 0; i --) cout << dp[n][i];
    return 0;
}
编辑于 2020-03-13 16:22:06 回复(2)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
string addstr(string str1,string str2){
    string &longstr=str1.size()>=str2.size()? str1:str2;
    string &shortstr=str1.size()<str2.size()? str1:str2;
    string sum;
    shortstr.insert(0,longstr.size()-shortstr.size(),'0');//对齐位数
    sum.resize(str1.size()+str2.size());    //预留空间
    int up=0,i=shortstr.size()-1,j=longstr.size()-1,k=sum.size()-1;
    while(i>=0){
        int temp=shortstr[i--]-'0'+longstr[j--]-'0';
        sum[k--]=(temp+up)%10+'0'; //只保存个位
        up=(temp+up)/10;    //保存进位
    }
    if(up!=0)
        sum[k--]=up+'0';
    sum=sum.substr(k+1);
    return sum;
}
int main(){
    int n;
    cin>>n;
    vector<string> dp;
    dp.resize(n+1);
    dp[0]=dp[1]=dp[2]="1";
    for(int i=3;i<=n;i++){
        dp[i]=addstr(dp[i-1],dp[i-3]);
        cout<<dp[i]<<endl;
    }
    cout<<dp[n];
}

编辑于 2019-10-21 08:57:10 回复(0)
Python
Sheerloock头像 Sheerloock 
import sys
def diffroad(n):
    # n<3  索引位置：n-1
    # n>=3  索引位置：(n-1)%3
    res = [1,1,2]
    if n<3:
        return 1
    if n==3:
        return 2
    # f(n) = f(n-1)+f(n-3）
    for i in range(4,n+1):
        res[(i-1)%3] += res[(i+1)%3]
    return res[(n-1)%3]

if __name__=="__main__":
    n = int(sys.stdin.readline().strip())
    print(diffroad(n))
    

编辑于 2019-09-07 22:34:25 回复(0)
Chimney头像 Chimney
python做大数据的题和作弊差不多 
steps = int(input())
count = [1, 1, 2]
for i in range(4, steps + 1):
    count[(i - 1) % 3] += count[(i + 1) % 3]
print(count[(steps - 1) % 3])


发表于 2019-08-29 15:48:27 回复(0)
Python
jamke头像 jamke

【企业真题】【小米】爬楼梯2

思路：

    使用排列组合（杀死脑细胞），考虑一次跳3级，两次跳3级，......以此类推

代码：

     
import sys

try:
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break
        n=int(line)
        if 100<=n<500:
            sum=0
            for i in range(1,n//3):
                res=1
                for j in range(2*i,3*i):
                    res*=(n-j)
                for k in range(1,i+1):
                    res//=k
                sum+=res
            if n%3==0:
                sum+=2
            elif n%3==1:
                sum+=n//3+2
            else:
                res=1
                for i in range(1,n//3+1):
                    res=res*(n//3+3-i)//i
                sum+=res+1
            print(sum)
except:
    pass


参考评论区的思路：

    找规律，发现：f(n)=f(n-1)+f(n-3)

代码：

     
line = input()
if line == '':
    print(None)
n = int(line)
if 100 <= n < 500:
    a = [1, 1, 2]
    for _ in range(n-3):
        a = [a[1], a[2], a[0] + a[2]]
    print(a[2])


发表于 2019-08-22 17:20:32 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
string dp[500];
// dp,用字符串就好
string add(string a,string b)
{
    while(a.size()<b.size())
        a = '0' + a;
    while(b.size()<a.size())
        b = '0' + b;
    int len = a.size();
    int carry = 0;
    string res = "";
    for(int i=len-1;i>=0;i--)
    {
        int temp = carry + a[i] - '0' + b[i] - '0';
        res = to_string(temp%10) + res;
        carry = temp/10;
    }
    while(carry)
    {
        res = to_string(carry%10) + res;
        carry/=10;
    }
    return res;
}
int main()
{
    //memset(dp,0,sizeof(dp));
    dp[0]="1";
    dp[1]="1";
    dp[2]="1";
    int n;
    cin>>n;
    for(int i=3;i<=n;i++)
        dp[i]=add(dp[i-3],dp[i-1]);
    cout<<dp[n]<<endl;
    return 0;
}

发表于 2019-08-16 18:39:05 回复(0)
Python
北雷北雷头像 北雷北雷

大数题用python很犯规，引入滚动数组

steps = int(input())

count = [1,1,2]
for i in range(4,steps+1):
    temp = count[0]+count[2]
    count[0] = count[1]
    count[1] = count[2]
    count[2] = temp

print(count[-1])
发表于 2019-08-07 15:07:51 回复(0)
Python
nbgao头像 nbgao 
n = int(input())
a = [0]*(n+1)
for i in range(3):
    a[i] = 1
for i in range(3, n+1):
    a[i] = a[i-1] + a[i-3]
print(a[n])

发表于 2019-07-31 23:22:53 回复(0)
Python
ElonB头像 ElonB 
"""
台阶问题考虑动态规划
每次仅可往上爬1或3级台阶
当前台阶方法数 = 所有一次可到达当前台阶方法数的和
dp[n] = dp[n-1]+dp[n-3]  ( n-t>=0,dp[0]=1 )
"""
if __name__ == "__main__":
    n = int(input().strip())
    dp = [1, 1, 1]
    for i in range(3, n + 1):
        dp.append(dp[i - 1] + dp[i - 3])
    print(dp[n])

发表于 2019-07-16 11:54:47 回复(1)
Polestar_a头像 Polestar_a 
n = int(input())
res = [0]*(n+1)
res[1],res[2],res[3] = 1,1,2
for i in range(4,n+1):
    res[i] = res[i-1]+res[i-3]
print(res[n])

发表于 2019-07-13 10:20:45 回复(0)
Python3
TS9527头像 TS9527
Python直接动规 

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        schemes = [1, 1, 2]
        if n < 4:
            print(schemes[n - 1])
            return
        # Traverse
        for _ in range(n - 3):
            schemes.append(schemes[0] + schemes[-1])
            schemes.pop(0)
        print(schemes[-1])


if __name__ == '__main__':
    M = MainActivity()
    M.main()
发表于 2024-09-02 21:21:41 回复(0)
森林雪兔头像 森林雪兔 
data = [0 for n in range(500)]

def getWays(stairs):
	if stairs <= 2:
		return 1
	if stairs == 3:
		return 2

	if data[stairs - 1] == 0:
		data[stairs - 1] = getWays(stairs - 1)
	if data[stairs - 3] == 0:
		data[stairs - 3] = getWays(stairs - 3)
	step1 = data[stairs - 1]
	step3 = data[stairs - 3]
	return step1 + step3;

num = int(input())
print(str(getWays(num)))

发表于 2020-07-25 13:51:14 回复(0)
offer+++11头像 offer+++11 
import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        //为什么要三个，因为n阶楼梯，只和前三个相关，也就是我后面的只要存住当前位置的前三个数，那么后面需要的时候还能取到。
        BigInteger dp1 = new BigInteger("1");
        BigInteger dp2 = new BigInteger("1");
        BigInteger dp3 = new BigInteger("1");
        Map<Integer,BigInteger> map  = new HashMap<>();
        map.put(1,dp1);
        map.put(2,dp2);
        map.put(3,dp3);
        for(int i=4;i<=n;i++){
          //将当前位置的前三阶的数量加上当前位置的前一阶的数量
             BigInteger dp4 = new BigInteger("0");
             BigInteger dp5 = new BigInteger("0");
             dp4=dp4.add(map.get(i-1));
             dp5=dp5.add(map.get(i-3));
             map.put(i,dp4.add(dp5));
        }
        System.out.println(map.get(n));
    }
hashmap模拟dp表为什么不能通过？有没有大佬解释一下
编辑于 2020-06-20 22:10:11 回复(0)
提交观点

问题信息

动态规划 运维工程师 小米集团 2019 递归
来自：小米2019秋招运维工...
上传者：小小
难度：
37条回答 10116浏览

热门推荐

通过挑战的用户

查看代码

相关试题

爬楼梯2

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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