1190：上台阶

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

1
2
3
4
0

【输出样例】

1
2
4
7

解析：当我们走到第i个台阶时，有三种情况，一是从i-3阶一步走三个台阶，二是从i-2阶一步走两个台阶，三是从i-1阶一步走一个台阶。所以递推关系式就是 ans[i]=ans[i-1]+ans[i-2]+ans[i-3]

注意数据范围可能超过int，要用long long

详见代码：

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans[105];
int main () {
    ans[1]=1;
    ans[2]=2;
    ans[3]=4;
    for(int i=4;i<=71;i++){
        ans[i]=ans[i-1]+ans[i-2]+ans[i-3];
    }
    while(cin>>n){
        if(n==0) break;
        cout<<ans[n]<<endl;
    }
	return 0;
}