ACM模版

描述

题解

可以考虑为两种情况，一种是竖着放一个，则前边的位置有F[n - 1]种，另一种是横着放两个，则前边的位置有F[n - 2]种，由此可以发现这里的F[n]符合斐波那契数列，所以F[n] = F[n - 1] + F[n - 2]。

代码

#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e3 + 10;

unsigned int Fibonacci[MAXN];

int main(int argc, const char * argv[])
{
    Fibonacci[0] = Fibonacci[1] = 1;

    int n;
    cin >> n;

    for (int i = 2; i <= n; i++)
    {
        Fibonacci[i] = (Fibonacci[i - 1] + Fibonacci[i - 2]) % MOD;
    }
    std::cout << Fibonacci[n] << '\n';

    return 0;
}