积木画
f[i] = f[i - 1] + f[i - 2] + g[i - 2]
f[i - 2]:
f[i - 1]
g[i - 2]
另一个都在g[i - 2]中计算过
g[i] = 2 * f[i - 1] + g[i - 1]
f[i - 1]
两个需要*2
g[i - 1]
另一个在g[i - 1]中被计算过
import java.util.Scanner;
public class Main {
static final int N = (int)1e7 + 10, mod = 1000000007;
static long[] f = new long[N], g = new long[N];
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
/*
初始化:
f[0] = f[1] = 1;
没有的话不放就是一种方案,2 * 1竖着放1中方案
g[1] = 1表示第2列空一格的方案也就是2种
*/
f[0] = f[1] = 1;
g[1] = 2;
for (int i = 2; i <= n; i++) {
f[i] = (f[i - 1] + f[i - 2] + g[i - 2]) % mod;
g[i] = (g[i - 1] + 2 * f[i - 1]) % mod;
}
System.out.println(f[n]);
}
}