题目描述

小明现在手里有3种数字卡片，卡片上的数字分别为1，2，3，3种数字卡片每种都有若干张,他想将这些数字放入有一个N*3的方格中，每个方格中只能放入一张卡片，且要求相邻的上下左右方格不能放入同一种数字的卡片，现在问你有多少种可能的放入方案。

输入描述：

每个文件输入第一行输入一个整数T(1<=T<=500)，代表有T组测试数据;

接下来T组，每一组输入一个整数n(1<=n<=100000);

输出描述：

对于每一组测试数据，输出一个答案代表可能的方案数，由于答案很大，请你对10^9+7取余;

示例1：

输入：

2

1

2

输出：

12

54

说明：

对于样例第一组放入1*3的方格中，可能的方案有：(1,2,1)、(2,1,2)、(3,1,2)、(1,2,3)、(2,1,3)、(3,1,3)、(1,3,1)、(2,3,1)、(3,2,1)、(1,3,2)、(2,3,2)、(3,2,3)

先上代码

import java.util.Scanner;

public class Main {

private static long[][] dp = new long[10001][2];

private static int now = 1;

public static void main(String[] args) {

dp[1][0] = 6L;

dp[1][1] = 6L;

Scanner sc = new Scanner(System.in);

int t = sc.nextInt();

for(int i = 0 ; i < t ; i++){

int n = sc.nextInt();

if(n<=now){

long res = (dp[n][0] + dp[n][1])%1000000007;

int realRes = (int) res;

System.out.println(realRes);

} else {

for(int j = now+1 ; j <= n ; j++){

dp[j][0] = (dp[j-1][0]*3 + dp[j-1][1]*2)%1000000007;

dp[j][1] = (dp[j-1][0]*2 + dp[j-1][1]*2)%1000000007;

}

long res = (dp[n][0] + dp[n][1])%1000000007;

int realRes = (int) res;

System.out.println(realRes);

now = n;

}

}

}

}

解题思路

第一想法是用dfs去做，但是肯定超时，上面也都提示了答案可能很大，所以dfs一个一个数肯定不行。

仔细分析题目给的示例输入，可以发现这样一个规律，2 * 3方格的方案都是由1 * 3方格方案拓展而来的！也就是说对于n * 3问题，我们只需要在n-1 * 3的方案基础上，对每个方案来考虑最后一排能扩展出几个方案即可。

而对于每一排的方案我们可以将其分为两大类：

第一类：(1,2,1)、(2,1,2)、(3,1,3)、(1,3,1)、(2,3,2)、(3,2,3)。我们把这种称为ABA类；

第二类：(3,1,2)、(1,2,3)、(2,1,3)、(2,3,1)、(3,2,1)、(1,3,2)。我们把这种称为ABC类

下面推导一下前一排和后一排的关系

如果前一排为ABA，那么后一排有5种可能，分别为 (C,A,C)、(B,A,B)、(B,C,B)、(B,A,C)、(C,A,B)。而这五种方案实际上就是 3种ABA 和 2种ABC ；

如果前一排为(A,B,C)，那么后一排有4种可能，分别为(B,A,B)、(B,C,B)、(B,C,A)、(C,A,B)。而这四种方案实际上就是 2种ABA 和 2种ABC ；

所以我们假设n * 3问题为f(n) ， ABA 方案数量为Xn，ABC 方案数量为Yn。

那么递推关系如下：

f(n+1) = Xn+1 + Yn+1；

Xn+1 = 3Xn + 2Yn；

Yn+1 = 2Xn + 2Yn；

最后可以用备忘录dp来记录之前计算过的问题，来防止重复计算，提高时间效率。

笔者为了防止溢出，用long类型来计算，并在每个地方都进行取余操作(应该不是很有必要)。

总结

总体上来说，阿里笔试题难度不低，题目类型与CCF、ACM竞赛类题目类似，和力扣上剑指offer的题目不是一个风格。之前只在力扣上刷了剑指offer和前200题，感觉只能应付面试过程中出的算法题。考前去牛客熟悉一下编程环境很重要，不然处理输入就要花费好长时间了。

————————————————来源|CSDN|D.monster