题目

暗黑字符串

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

样例输入：
2
3
样例输出：
9
21

题目链接

思路

我们这里就不复述题目的意思了，直切正题，这是一道DP的题目，绞尽脑汁，虽然看了一些博客，但是感觉讲的不详细，最后请教同学才明白，所以讲思路共享出来。
这里需要列出一个dp的式子，那么我们假设S(n)是第n个所拥有的暗黑的字符串的个数，他的个数一定依赖于S(n-1)和S(n-2)，现在我们做个拆分，将S(n-1)拆分为S(相同)和S(不同)，即S(n-1) = S(相同)+S(不同)。假设n-1和n-2是相同的，那么肯定是S(相同)3，如果n-1和n-2是不同的呢，一定是S(不同)2。现在等式就是S(n) = S(相同)3 + S(不同)2。现在问题来了，S(相同)和S(不同)是什么关系呢，当n-1和n-2相同的时候S(相同) = S(n-2)，当n-1和n-2不同的时候，S(不同) = S(n-1)-S(相同) = S(n-1) - S(n-2)。划归到总式子，就是S(n) = 3S(n-2)+2[S(n-1)-S(n-1)] = 2*S(n-1)+S(n-2)

代码

//
//  main.cpp
//  网易2017秋招笔试题集合一_暗黑的字符串
//
//  Created by 李林 on 2017/2/20.
//  Copyright © 2017年 lee. All rights reserved.
//

#include <iostream>
#include <cmath>
using namespace std;

class Solution{
public:
    long long calculateCount(int N){
        if(N == 1)    return 3;
        else if(N == 2) return 9;
        else{
            return 2*calculateCount(N-1)+calculateCount(N-2);
        }
    }
private:
    
};

int main(int argc, const char * argv[]) {
    
    Solution s;
    int N;
    scanf("%d", &N);
    
    long long result = s.calculateCount(N);
    printf("%lld", result);
    
    return 0;
}

代码上传到了github