首页 > 试题广场 > 爬楼梯2
[编程题]爬楼梯2
在你面前有一个n阶的楼梯(n>=100且n<500),你一步只能上1阶或3阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯(到最后一层为爬完)。

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


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

输入

100

输出

24382819596721629

备注:
注意时间限制
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 回复(1)
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)
import java.util.Scanner;
import java.math.BigInteger;
import java.util.Arrays;

public class Main {
   static BigInteger[] a;
    public static BigInteger getRes(int k) {
        if(k==2 ||k==1||k==0){
            return new BigInteger("1");
        }
        if(k>2){
            if(0==a[k-3].compareTo(new BigInteger("0"))){
                a[k-3]=getRes(k-3);
                return getRes(k-1).add(getRes(k-3));
            }
            return getRes(k-1).add(a[k-3]);
           }
        return new BigInteger("0");
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        a = new BigInteger[q];
        Arrays.fill(a,BigInteger.ZERO);
        BigInteger count = getRes(q);
        System.out.print(count);
    }
}
发表于 2019-09-17 14:43:40 回复(0)
#include <bits/stdc++.h>
using namespace std;

void StrAdd(string& sum, string &a, string &b){
    int carry = 0;
    int a_num, b_num;
    string::iterator a_iter, b_iter;
    for(a_iter = a.begin(), b_iter = b.begin(); a_iter != a.end() && b_iter != b.end(); ++a_iter, ++b_iter){
        a_num = *a_iter - '0';
        b_num = *b_iter - '0';
        sum.append(1, '0'+(a_num + b_num + carry)%10);
        carry = (a_num + b_num + carry) / 10;
    }
    while(a_iter != a.end()){
        a_num = *a_iter - '0';
        sum.append(1, '0'+(a_num + carry)%10);
        carry = (a_num + carry) / 10;
        ++a_iter;
    }
    while(b_iter != b.end()){
        b_num = *b_iter - '0';
        sum.append(1, '0'+(b_num + carry)%10);
        carry = (b_num + carry) / 10;
        ++b_iter;
    }
    if(carry)
        sum.append(1, '1');
    return;
}

int main(void){
    int x;
    vector<string> dp(501);
    dp[0] = "1";
    dp[1] = "1";
    dp[2] = "1";
    cin>>x;
    for(int i =3; i < 501; ++i)
        StrAdd(dp[i], dp[i-1], dp[i-3]);
    reverse(dp[x].begin(), dp[x].end());
    cout<<dp[x]<<endl;
    return 0;
}
字符串实现的大数相加
发表于 2019-09-06 20:37:14 回复(0)
python 3
tmp=[1,1,1]
N=int(input())
for i in range(N-2):
    tt=tmp[0]+tmp[2]
    tmp[0]=tmp[1]
    tmp[1]=tmp[2]
    tmp[2]=tt

print(tmp[2])


发表于 2019-09-03 10:59:44 回复(0)
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int number;
    cin >> number;
    int a = 0, b = 1, c = 2;
    vector<vector<char>> vvData(3, vector<char>{1});

    for(int curNum = 3; curNum <= number; curNum++)
    {
        int d = (c+1)%3;
        a = b;
        b = c;
        c = d;

        int carry = 0;
        for(size_t i=0; i < vvData[c].size() || i < vvData[b].size() || carry!=0; i++)
        {
            if(i >= vvData[c].size())
                vvData[c].push_back(0);
            vvData[c][i] += ((i < vvData[b].size())?vvData[b][i]:0) + carry;
            carry = vvData[c][i]/10;
            vvData[c][i] = vvData[c][i]%10;
        }
    }

    for(auto iter = vvData[c].rbegin(); iter!=vvData[c].rend(); iter++)
        cout << (int)(*iter);
    cout << endl;
    
    return 0;
}

发表于 2019-09-02 16:54:55 回复(0)
采用动态划分算法
使用大整数数组BigInteger[] a 存放已经计算的值
算法公式  a[i] = a[i-1]+a[i-3]
public static BigInteger JumpFloor(int target){
        BigInteger[] a = new BigInteger[target+1];
        a[0] = BigInteger.valueOf(1);
        a[1] = BigInteger.valueOf(1);
        a[2] = BigInteger.valueOf(1);
        a[3] = BigInteger.valueOf(2);
        int i = 4;
        for(i = 4;i<=target;i++) {
            a[i] = a[i-1].add(a[i-3]);
        }
        return a[target];
        
    }
发表于 2019-08-23 17:25:01 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
string add(string dp1,string dp2){
    string res="";
    int i=dp1.size()-1,j=dp2.size()-1,k=0;
    vector<int>data(max(dp1.size(),dp2.size())+1);
    fill(data.begin(),data.end(),0);
    int bit=0;
    for(;i>=0||j>=0;--i,--j){
          if(i>=0&&j>=0){
            data[k++]=dp1[i]-'0'+dp2[j]-'0';
            }
        else if(i>=0){
            data[k++]=dp1[i]-'0';
            }
        else if(j>=0){
            data[k++]=dp2[j]-'0';
            }
    }
    for(int t=0;t<k||bit;++t){
        if(bit){
            res+=to_string((data[t]+bit)%10);
            bit=(data[t]+1)/10;
        }
        else{
            res+=to_string(data[t]%10);
            bit=data[t]/10;
        }
    }
    return string(res.rbegin(),res.rend());
}
int main()
{
    int n;
    cin>>n;
    vector<string>dp(n+1);
    dp[0]="0";
    dp[1]="1";
    dp[2]="1";
    dp[3]="2";
    if(n<=3) {
        cout<<dp[n]<<endl;
        return 0;
    }
    for(int i=4;i<=n;++i)
        dp[i]=add(dp[i-1],dp[i-3]);
    cout<<dp[n]<<endl;
    return 0;
}

发表于 2019-08-22 20:13:25 回复(0)

 public static BigInteger TJ(int n){
        if(n==1||n==2) {
            return BigInteger.valueOf(1);
        }
        if(n==3) {
            return BigInteger.valueOf(2);
        
        BigInteger a=BigInteger.valueOf(1);
        BigInteger b=BigInteger.valueOf(1);
        BigInteger c=BigInteger.valueOf(2);
        BigInteger temp=BigInteger.valueOf(0);
        for(int i=n;i>3;i--) {
            temp=a.add(c);
            a=b;
            b=c;
            c=temp;
        }
        return temp;
    }
发表于 2019-08-16 10:44:10 回复(1)
n = int(input())
import sys
import functools
sys.setrecursionlimit(1000000)
@functools.lru_cache(None)
def fibonacci(n):
    if n < 3:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 3)
print(fibonacci(n))
发表于 2019-08-13 17:01:41 回复(0)
def helper(n):
    dp = list(0 for _ in range(n+1))
    dp[1] = 1
    dp[2] = 1
    dp[3] = 2
    for i in range(4,n+1):
        dp[i] = dp[i-1]+dp[i-3]
    return dp[n]
n = int(input())
print(helper(n))

发表于 2019-08-09 08:27:58 回复(0)
//    本题设置的数目范围有点大,所以不能使用递归调用,非递归方法就是把前面计算的结果保留,避免重复计算
//    非递归方法
public static long get_step2(int n)
      { long []a = new long[n+1]; 
       a[0]=1;   
       a[1]=1;   
       a[2]=1;  
       a[3] =2;  
       for (int i = 4; i <=n; i++)
             {
                  a[i]= a[i-1]+a[i-3];   
             }  
       return a[n];
      }




发表于 2019-08-08 12:56:56 回复(0)