网易2017暗黑的字符串题

题目：

一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：
BAACAACCBAAA 连续子串"CBA"中包含了'A','B','C'各一个，所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含'A','B','C',所以是暗黑的字符串
你的任务就是计算出长度为n的字符串(只包含'A'、'B'和'C')，有多少个是暗黑的字符串。

分析：

1、当n=1的时候，暗黑个数为3；当n=2的时候暗黑字符串为9
2、当n=3的时候，利用排列组合，得出3x3+3x2x2 = 21种情况，
3x3表示XXY型，XX可以是AA、BB、CC，当XX确定后，Y可以是ABC中的任何一个。3x2x2，表示XY_型，先确定X有三种情况，Y不和X一样只能有两种情况，第三个位置必须和前面两个位置中其中的一个相同，所有有两种情况
4、当n=4的时候，先确定前三位，当XXX_，有3x3种可能，当XX_ _时（AABA，AABB，.....），XX位置有三种可能，第三位有两种可能，第四位有两种可能，有3x2x2种可能。同理，有XXX有3x3种可能， XX有3x2x2种可能。当XY时，（X，已经在XXX和XXX中包含，同理Y也已经被包含）X位置有三种可能，Y位置也有三种可能，共3x3种可能
5、 n=1 暗黑个数=3
n=2 暗黑个数=9
n=3 暗黑个数=3x3+3x2x2 = 21
n=4 暗黑个数=2x（3x3+3x2x2）+3*3 = 2x21+9
由此发现：n=3的暗黑数是n=2时的暗黑数的2倍加上n=1时候的暗黑数
n=4的暗黑数是n=3时的暗黑数的2倍加上n=2时候的暗黑数

public static long cal(int n){
        if(n==1)
            return 3;
        else if(n==2)
            return 9;
        
        return 2*cal(n-1)+cal(n-2);
    }