题目地址：http://hihocoder.com/problemset/problem/1318
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。
小Hi想知道在所有 n 位二进制数（一共有2n个）中，非法二进制数有多少个。
例如对于 n = 3,有 011, 110, 111 三个非法二进制数。
由于结果可能很大，你只需要输出模109+7的余数。
输入
一个整数 n (1 ≤ n ≤ 100)。
输出
n 位非法二进制数的数目模109+7的余数。
样例输入
3
样例输出
3
Java代码如下：
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);int n=in.nextInt();long[] dp=new long[n+10];dp[1]=0;dp[2]=1;int temp=1;for(int i=3;i<=n;i++){temp=(temp*2)%(int)(Math.pow(10, 9)+7);dp[i]=(dp[i-1]+dp[i-2]+temp)%(int)(Math.pow(10, 9)+7);}System.out.println(dp[n]);}}
思路：这也是一个dp的题，根据n-1和n-2的结果可以算出n的值。
值得注意的是：java int范围是 -2147483648~2147483647
所以2个（10^9+7）求模后的结果相加不会溢出，但是3个相加就可能溢出，所以要用long来存。