51nod-1031 骨牌覆盖

发表于 动态规划 分类,标签:

 

在2*N的一个长方形方格中,用一个1*2的骨牌排满方格。
问有多少种不同的排列方法。

例如:2 * 3的方格,共有3种不同的排法。(由于方案的数量巨大,只输出 Mod 10^9 + 7 的结果)
Input
输入N(N <= 1000)
Output
输出数量 Mod 10^9 + 7
Input示例
3
Output示例
3



思路:斐波纳契数列。。。


代码:

#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include <string.h>

#define LL long long
#define MAX 1e9
#define mod 1000000007
using namespace std;
int s[1005];
int main()
{
    int n;
    scanf("%d",&n);
    s[1]=1;
    s[2]=2;
    for(int i=3;i<=n;i++)
    {
        s[i]=(s[i-1]+s[i-2])%mod;
    }
    printf("%d\n",s[n]);

    return 0;
}


0 篇评论

发表我的评论