首页 > 试题广场 >

爬楼梯2

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

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


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

输入

100

输出

24382819596721629

备注:
注意时间限制
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)
矩阵快速幂
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)
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)
#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)
动态规划,当前阶梯可能是前一阶跨上来的,也可能是前三阶跨上来的
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)
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)
/*
*参考大佬的代码写的,在此处感谢 @夏夜飘雪
* 链接: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)

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)
#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)
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)
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)

【企业真题】【小米】爬楼梯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很犯规,引入滚动数组

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)
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)
"""
台阶问题考虑动态规划
每次仅可往上爬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)
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)
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)
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)
//动态规划 和 字符串相加  写错一个地方 调了老半天
#include<iostream>
(720)#include<string>
#include<vector>


using namespace std;

string StringAdd(string a, string b) {
	string ans;
	int i = a.size() - 1;
	int j = b.size() - 1;

	int jinwei = 0;
	while (i >= 0  || j >= 0) {
		
		int num1 = i >= 0 ? a[i] - '0' : 0;
		int num2 = j >= 0 ? b[j] - '0' : 0;

		int sum = num1 + num2 + jinwei;
		int mod = sum % 10;
		string smod = to_string(mod);

		jinwei = sum / 10;
		ans = smod + ans;
		i--;
		j--;	
	}

	if (jinwei > 0) {
		string sjinwei = to_string(jinwei);
		ans = sjinwei + ans;
	}
	return ans;
}

int main(void) {
	int n;
	cin >> n;
	vector<string> dp(n + 1);

	if (n == 1 || n == 2) {
		cout << "1" << endl;
		return 0;
	}
	dp[0] = "1";
	dp[1] = "1";
	dp[2] = "1";
	for (int i = 3; i <= n; i++) {
		dp[i] = StringAdd(dp[i-1], dp[i - 3]);
		
	}
	cout << dp[n] << endl;

	return 0;
}

发表于 2020-05-09 21:27:51 回复(0)