本系列文章是关于《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算法竞赛基础算法》的文章！希望对大家有帮助！