本系列文章是关于《ACM-ICPC算法竞赛基础算法》的文章！
零、题目介绍
有排成一行的n个方格（ 0 < n <= 50），用红、粉、绿三种颜色涂每个格子， 每格涂一色，要求任何相邻的方格不能同色,且首尾两格也不同色， 求所有满足要求的涂法。
一、题目思路及解析
1、采用递推法。 2、设置一函数f(n).前（n - 2）个格子已涂好后，涂第（n - 1） 个格子有两种情况： （1）第（n - 1）个 格子的颜色与第（n - 2）个格子和第1个格子的颜色都不同，那么第n个格子就是剩下的那个颜色，没有选择。也就是说f(n - 1). （2）第（n - 1）个格子的颜色与第（n - 2）个格子的颜色不同，但是与第1个格子的颜色相同，那么第n个格子的颜色就有两个颜色可以选择，也就是f(n - 2) * 2. 3、综上所述，f(n) = f(n - 1) + 2 * f(n - 2).
示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
二、代码如下：import java.util.Scanner;
public class SquareColoring {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long[] arr = new long[51];
arr[1] = 3;
arr[2] = 6;
arr[3] = 6;
for(int i = 4; i < 51; ++i)
{
arr[i] = 2 * arr[i - 2] + arr[i - 1];
}
System.out.println(arr[(int)n]);
}
}
总结
每天都会更新一篇关于《ACM-ICPC算法竞赛基础算法》的文章！希望对大家有帮助！
