P10250 [GESP样题 六级] 下楼梯 题解

· · 题解

题目传送门

修改了思路里的一处笔误，望管理通过。

题意

就是让你求下 n 级台阶时有一次下一级，一次下两级，一次下三级这三种方式，一共多少种走法，且顺序不同也算两种哦！要注意。

递推思路

就是一个简单的递推题，当 n=1 时，那当然就是直接下一级台阶，当 n=2 时，可以直接下两级，也可以下两个一级，当 n=3 时，可以下三级，也可以先下一级再下两级，也可以先下两级后再下一级，也可以连续下三个一级，后面楼梯级数每增加一级方案数就是数组前三个元素的和，可得以下公式：

a_j=a_{j-1}+a_{j-2}+a_{j-3}

其实这个公式是很容易得到的，因为一次最多下三级楼梯，所以从上往下数第 j 级楼梯可以从上面三级中任意一级走过来，自然就可以得到是方案数是上面三级楼梯方案数的和。

递推代码

#include<bits/stdc++.h> 
using namespace std;

long long a[1001];
int n;
int main(){
    cin>>n;
    a[0]=1;
    a[1]=2;
    a[2]=4;
    for(int j=3;j<n;j++){
        a[j]=(a[j-1]+a[j-2]+a[j-3]);
    }
    cout<<a[n-1]<<endl;     
    return 0;
}