1. 描述

仅由三个字符A、B、C构成字符串，且字符串任意相邻三个元素不能完全相同。如“ACCCAB”不合法，“ABBCBCA”合法。求满足条件的长度为n的字符串个数。假定不考虑整数溢出，要求时间和空间复杂度不高于O(N)。

2. Hints

  • 1、考虑使用动态规划，将长度为N的字符串个数表示成长度为N-1的字符串个数的递归关系；
  • 2、使用滚动数组降低空间复杂度；
  • 3、矩阵乘幂降低时间复杂度。

3. Solution

若当前已经有长度为n-1的合法字符串，则在末端增加一个字符，形成长度为n的字符串，n-1的字符串可分为“末端两字符相等”和“末端两字符不等”，分别记为\(dp[n-1][0]\)和\(dp[n-1][1]\)，长度为n的字符串都可以这样划分，于是:
$$
\begin{cases}
dp[n][0] = dp[n-1][0]*2 + dp[n-1][1]*2 \\
dp[n][1] = dp[n-1][0]
\end{cases}
$$
其初始条件为\(dp[1][0] = 3, dp[1][1] = 0\);

状态转移方程为
$$
\begin{cases}
dp[n][0] = dp[n-1][0]*2 + dp[n-1][1]*2 \\
dp[n][1] = dp[n-1][0]
\end{cases}
$$
其可以通过滚动数组简化：
$$
\begin{cases}
dp[0] = dp[0]*2 + dp[1]*2 \\
dp[1] = dp[0]
\end{cases}
$$
由此可以将空间复杂度降为O(1)

4. 代码

#include<iostream>
using namespace std;

int calculateCount(int);
int main(int argc, char** argv) {
    int n;
    cin >> n;

    int accumulation = calculateCount(n);
    cout << accumulation << endl;
    return 0;
}

int calculateCount(int n) {
    int accumulation = 0;
    int dp0 = 3, dp1 = 0;

    for(int i = 1; i < n; i++) {
        int temp = dp0;
        dp0 = 2*dp0 + 2*dp1;
        dp1 = temp;
    }
    
    accumulation = dp0+dp1;

    return accumulation;
}

5. 优化

此题还可以简化时间复杂度，方法就是题目中的提示3。
由矩阵的状态方程：
$$
\begin{cases}
dp[0] = 2*dp[0] + 2*dp[1] \\
dp[1] = dp[0]
\end{cases}
$$
得到矩阵形式：
$$
\begin{equation}
(dp[0] dp[1])_{new} = (dp[0] dp[1])_{old} \cdot \bigl( \begin{matrix} 2 & 1 \\ 2 & 0 \end{matrix} \bigr)
\nonumber
\end{equation}
$$
从而得到：
$$
\begin{equation}
\begin{split}
(dp[0] dp[1])_{n} &= (dp[0] dp[1])_{n-1} \cdot \bigl( \begin{matrix} 2 & 1 \\ 2 & 0 \end{matrix} \bigr) \\
&= (dp[0] dp[1])_{n-2} \cdot \bigl( \begin{matrix} 2 & 1 \\ 2 & 0 \end{matrix} \bigr) \bigl( \begin{matrix} 2 & 1 \\ 2 & 0 \end{matrix} \bigr) \\
&= \ldots \\
&= (dp[0] dp[1])_{1} \cdot \bigl( \begin{matrix} 2 & 1 \\ 2 & 0 \end{matrix} \bigr)^{n-1}
\end{split}
\nonumber
\end{equation}
$$

新建一个矩阵求幂的类，并据此写出完整代码，以下只给出类实现:

#ifndef POWMATRIX_H
#define POWMATRIX_H

class PowMatrix {
    public:
        PowMatrix(int dimension);   //构造函数
        virtual ~PowMatrix();       //析构函数
        void setMatrix(int* matrix);    //设置矩阵
        int multiply(int row,int column);   //两数组对应相乘
        void pow(int count);        //求幂函数
        int* getResult() {          //得到结果
            return result;
        }
    private:
        int dimension;      //矩阵维度
        int* matrix;        //需要求幂的初始矩阵
        int* result;        //求幂之后存放结果的矩阵
};

#endif // POWMATRIX_H


PowMatrix::PowMatrix(int dimension) {
    this->dimension = dimension;            //初始化维度
    matrix = new int[dimension*dimension];  //初始化分配matrix空间
    result = new int[dimension*dimension];  //初始化分配存放结果的矩阵的内存空间
}

PowMatrix::~PowMatrix() {
    delete matrix;
    delete result;
}

void PowMatrix::setMatrix(int* matrix) {    //设置需要自乘的矩阵值,用一维数组形式逐行存放
    int len = dimension*dimension;
    for(int i = 0; i < len; i++) {
        (this->matrix)[i] = matrix[i];
    }
}

int PowMatrix::multiply(int row, int column) {  //result矩阵第row行和matrix矩阵第column列相乘
    int val = 0;
    for(int i = 0, j = 0; i < dimension; i++,j++) {
        val += ( result[row*dimension+i] ) * ( matrix[j*dimension+column] );
    }
    return val;
}

void PowMatrix::pow(int count) {                //矩阵求幂函数
    //以下为建立单位矩阵
    for(int i = 0; i < dimension*dimension; i++) {
        if(i/dimension == i%dimension) {        //判断一维数组模拟矩阵的实际对角线位置
            result[i] = 1;
        } else {
            result[i] = 0;
        }
    }
    //矩阵的count次幂
    for(int k = 0; k < count; k++) {            //第k次自乘
        int* temp = new int[dimension*dimension];
        //以下循环,逐次求出矩阵row行column列的值
        for(int row = 0; row < dimension; row++) {
            for(int column = 0; column < dimension; column++) {
                temp[row*dimension+column] = multiply(row,column);
            }
        }
        //将temp矩阵赋值给result矩阵,即更新result矩阵
        for(int j = 0; j < dimension*dimension; j++) {
            result[j] = temp[j];
        }
    }
}

代码可在此处下载