小乐乐走台阶

链接：http://pre.ac.nowcoder.com/acm/contest/1869/Q
来源：牛客网

题目描述

小乐乐上课需要走n阶台阶，因为他腿比较长，所以每次可以选择走一阶或者走两阶，那么他一共有多少种走法？
输入描述:

输入包含一个整数n (1 ≤ n ≤ 30)

输出描述:

输出一个整数，即小乐乐可以走的方法数。

小乐乐有两种走法，一次一个台阶或两个台阶，由此想到排列组合，以n=10时为例，如图
左边表示为一步走两个台阶的次数，小乐乐每走一次两个台阶便可少走一步
接下来先写一个排列组合的公式程序，如图
最后记得考虑sum的取值范围是longlong

#include<iostream>
using namespace std;
int  main()
{
    short n;
    long long sum = 0;
    cin >> n;
    for (int i = 0; n - i >= i; i++)
    {
        short t = n - i;
        long long p = 1, q = 1;
        for (int j = t; j > t - i; j--)
        {
            p *= j;
            q *= t - j + 1;
        }
        sum += p / q;
    }
    cout << sum << endl;
}