HDU_2046.骨牌铺方格

Problem Description

 

Date:

2009 / 05 / 08

 

Problem Analysis:

递推的题目。

从图中也可以观察出来，第N张牌的排列可以又N-1张牌的排列再在末尾加上一张竖的牌。这样依然合法。
也可以在N-2张合法排列的牌后面加上两张横着放的牌(如果竖着放就和上面一种重复了)。
所以f(n) = f(n-1) + f(n-2)
即是一个斐波那契数列。 用64位存哦。

 

Code:

 

#include
#include

int main(void)
{
    int i;
    __int64 d[51] = {1, 1, 2,};

    for (i = 3; i < 51; i++)
        d[i] = d[i-1] + d[i-2];
    while (scanf("%d", &i) != EOF)
        printf("%I64d\n", d[i]);

    return 0;
}

 

@fleap