三字母组合算法

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
题目：仅由三个字符A,B,C构成字符串,且字符串任意三个相邻元素不能完全相同.如"ACCCAB"不合法,"ABBCBCA"合法.
求：1. 满足条件的长度为n的字符串个数?
2. 假定不考虑整数溢出
3. 要求时间和空间复杂度不高于O(N)
解：令dp[n][0]表示结尾不相等/dp[n][1]表示结尾相等，则

1. 结尾不相等
   (1). n-1的字符串最后两个不相同,长度为n的字符串最后两个不相同: 如: ABCAABAB 后面只能再加A或C
   (2). n-1的字符串最后两个相同,长度为n的字符串最后两个不相同: 如: ABCAABABB 后面只再加A或C
   因此状态转移方程为:dp[n][0]=2dp[n-1][0]+2dp[n-1][1]
2. 要想使长度为n的字符串最后两个相同,则长度为n-1的字符串最后两个字符只能不相等,且只有一种情况
   ABCAAB 后面只能加B
   因此状态转移方程为: dp[n][1]=dp[n-1][0]
   初始条件：
   dp[1][0] = 3
   dp[1][1] = 0
   使用滚动数组，将空间复杂度由O(N)降到O(1)
   dp[0] = 2dp[0] + 2dp[1]
   dp[1] = dp[0]
   Java版本的实现如下：

public static int calcCount(int n){
        int nNonRepeat = 3;
        int nRepeat = 0;
        int t;
        for(int i=2;i<=n;i++){
            t = nNonRepeat;
            nNonRepeat = 2 * (nNonRepeat + nRepeat);
            nRepeat = t;
        }
        return nRepeat + nNonRepeat;
    }

还可以进一步优化，由状态方程得到矩阵表示如下：

矩阵形式表示
推导公式

Java版本的矩阵表示：

/**
 * 2*2的矩阵
 *
 */
class Matrix22{
    //第一列
    public int a;
    public int b;
    //第二列
    public int c;
    public int d;
    public Matrix22(int a, int b, int c, int d){
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }
}

/**
     * 矩阵相乘
     * @param mMatrix22
     * @param nMatrix22
     */
    public static Matrix22 matrixMulti(Matrix22 mMatrix22, Matrix22 nMatrix22){
        int a = mMatrix22.a * nMatrix22.a + mMatrix22.c * nMatrix22.b;
        int b = mMatrix22.b * nMatrix22.a + mMatrix22.d * nMatrix22.b;
        int c = mMatrix22.a * nMatrix22.c + mMatrix22.c * nMatrix22.d;
        int d = mMatrix22.b * nMatrix22.c + mMatrix22.d * nMatrix22.d;
        mMatrix22 = new Matrix22(a, b, c, d);
        return mMatrix22;
    }
/**
     * 矩阵的n次方
     * @param matrix22
     * @param n
     */
    public static Matrix22 matrixN(Matrix22 matrix22, int n){
        if (n == 0) {
            matrix22 = new Matrix22(1, 0, 0, 1);//单位阵
            return matrix22;
        }
        if (n == 1) {
            return matrix22;
        }
        if (n % 2 == 0) {//偶数
            matrix22 = matrixN(matrix22, n/2);
            matrix22 = matrixMulti(matrix22, matrix22);
        }else {//奇数
            Matrix22 xMatrix22 = matrix22;
            matrix22 = matrixN(matrix22, n/2);
            matrix22 = matrixMulti(matrix22, matrix22);
            matrix22 = matrixMulti(matrix22, xMatrix22);
        }
        return matrix22;
    }

public static int calcCount2(int n){
//      int nNonRepeat = 3;
//      int nRepeat = 0;
        Matrix22 matrix22 = new Matrix22(2, 2, 1, 0);
        matrix22 = matrixN(matrix22, n-1);
        return 3*(matrix22.a + matrix22.c);//(3 0)*m
    }

这样把时间复杂度降为O(logN)