题目
暗黑字符串
一个只包含'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
