GSEP 6级样题下楼梯

题目描述

顽皮的小明发现，下楼梯时每步可以走 1 个台阶、2 个台阶或 3 个台阶。现在一共有N个台阶，你能帮小明算算有多少种方案吗？

输入格式

输入一行，包含一个整数N。约定1 ≤ N ≤ 60。

输出格式

输出一行，包含一个整数C，表示方案数。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

#include <iostream>
using namespace std;

// 此题迭代方式类似斐波那契

// f(n) = f(n - 1) + f(n - 2) + f(n - 3)

int main()
{
    uint64_t a = 1, b = 2, c = 4;
    int n; cin >> n;
    if (n <= 3) {
        if (n == 1) cout << 1;
        else if (n == 2) cout << 2;
        else if (n == 3) cout << 4;
    
    } else {
        uint64_t t = 0;
        for (int i = 4; i <= n; ++i) {
            t = a + b + c;
            a = b;
            b = c;
            c = t;
        }
        cout << t;
    }
}