UVa 10359 - Tiling
传送门
题意
用2x1或者2x2的方格覆盖2xn的格子，有多少种方案。
思路
考虑加入第n列
显然可以放一个2x1的。这时候的方案数是$f(n - 1)$
可以把上一列移开，放两个横着的2x1，或者一个2x2。这时候的方案数是$f(n - 1) + 2 * f(n - 2)$
再移和加入的列就无关了。
所以最后得出公式
\[f(n) = f(n - 1) + 2 * f(n - 2)\]OEIS上也有。
代码
import java.math.*;
import java.io.*;
import java.util.*;
public class Main {
static public void main(String[] args) {
Scanner in = new Scanner(System.in);
BigInteger[] dp = new BigInteger[300];
dp[0] = BigInteger.ONE;
dp[1] = BigInteger.ONE;
dp[2] = BigInteger.valueOf(3);
for (int i = 3; i < 260; i++)
dp[i] = dp[i - 1].add(dp[i - 2].multiply(BigInteger.valueOf(2)));
while (in.hasNext()) {
int n = in.nextInt();
System.out.println(dp[n]);
}
}
}