6. 环形涂色
如上图,组成环形的格子需要涂3种颜色。
它们的编号分别是1~14
相邻的格子不能用相同的颜色。
涂色方案的数目是:24576
当格子数目为50的时候,求涂色方案总数。
【源代码】
【JAVA】
public class A
{
/*
static long f(int n){
if(n==1) return 3;
if(n==2) return 6;
return 2 * f(n-2) + f(n-1);
}
*/
public static void main(String[] args){
long[] f = new long[50+10];
f[1] = 3;
f[2] = 6;
for(int i=3; i<=50; i++){
f[i] = f[i-2] * 2 + f[i-1];
//①第二个与第n个同色时,第一个可以涂两种颜色 ②第二个与第n个不同色时,第一个可以涂一种颜色
}
for(int i=3; i<=50; i++){
System.out.println(i + ": " + f[i]);
}
}
}
未经允许不得转载!环形涂色(dp)