G-PC快脱单了（找规律|DP）

题目链接：http://acm.csust.edu.cn/problem/3027

Description

 

今年光棍不11

单身的Pc最讨厌的就是11月11日就是 我们所说的光棍节.

他不想看到所有 '11' 的存在,如果存在,pc就会很伤心

有天小学弟给了Pc 一个长度n的01串，小学弟并不想让Pc伤心。

现在你要帮小学弟求出有多少种长度为n且让pc不会伤心的01串 (数量可能很大，所以最后的结果对1e9 + 7取模)。

Input

 

一个整数 1≤n≤1e6

Output

 

一个整数，表示结果.

Sample Input 1 

1

Sample Output 1

2

---

看起来也是有点唬人...不过打个表就是一眼题了，我们会发现这就是一个首相为2的斐波那契数列，推出式子：

证明过程如下：

我们用dp[i][j]表示第i个位置放置j，那么我们很容易得出状态转移方程：

dp[i][j]=dp[i-1][k]若j为0，则k可以为0或者1，若j为1，则k为0，即：

dp[i][1]=dp[i-1][0];

dp[i][0]=dp[i-1][1]+dp[i-1][0];

即dp[i][] =dp[i-1][0]+dp[i-1][1]+dp[i-1][0]

　　       =dp[i-1][]+dp[i-2][1]+dp[i-2][0]

　　　　=dp[i-1][]+dp[i-2][]

证得：dp[i]=dp[i-1]+dp[i-2]

以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e6+10;
const int mod=1e9+7;

int f[mac];

int main()
{
    int n;
    scanf ("%d",&n);
    f[1]=2;f[2]=3;
    for (int i=3; i<=n; i++){
        f[i]=(f[i-1]+f[i-2])%mod;
    }
    printf ("%d
",f[n]);
    return 0;
}