三扔硬币

题目描述
扔 n 次硬币的结果可以用一串 0/1 序列来表示。给定 n，请统计有多少种扔硬币的结果中不含三个连续的 0 且不含三个连续的 1。

当 nn 较大的时候，答案可能很大，所以输出答案模 1,000,000,007 的余数即可。

输入格式
单个整数：表示 n。

输出格式
单个整数：表示答案模 1,000,000,007 的余数。

数据范围
对于 30% 的数据，1≤n≤20；
对于 60% 的数据，1≤n≤5000；
对于 100% 的数据，1≤n≤1,000,000。
样例数据
输入:
3
输出:
6

题解：

dp[i][1]表示第i个数为1的合法方案数。
dp[i][0]表示第i个数为0的合法方案数。
首先考虑转移dp[i][1]：
连续一个1，dp[i-1][0]。
连续两个1，dp[i-2][0]。
则有dp[i][1]=dp[i-1][0]+dp[i-2][0]。
然后考虑转移dp[i][0]：
连续一个0，dp[i-1][1]。
连续两个0，dp[i-2][1]。
则有dp[i][0]=dp[i-1][1]+dp[i-2][1]。

最后答案即为dp[n][0]+dp[n][1]。