其实一开始想法是3^3 = 27减去ABC的排列3 X 2 X 1 = 6，也就是21种。但是从这个角度一直考虑下去，其实是错的。
应该从n = 2的基础上分析。首先n = 3是从n =2的基础上扩展一位，首先我们假设后面两位是不同的（比如C、A）的那只能后面两位选其中一位。f(n) = 2 * f(n - 1)。但是考虑到最后两位一样的情况，f(n - 1)中有两位相同的数量，是f(n - 2)数量的个数，因为必须和f(n-2)的最后一位一样。
1 #include<iostream> 2 #include<cstdio> 3 #include <cctype> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 #include<string> 8 #include<cmath> 9 #include<set> 10 #include<vector> 11 #include<stack> 12 #include<queue> 13 #include<map> 14 using namespace std; 15 #define ll long long 16 #define mem(a,x) memset(a,x,sizeof(a)) 17 #define se second 18 #define fi first 19 const int INF= 0x3f3f3f3f; 20 const int N=1e7+5; 21 22 ll dp[34]; 23 int n; 24 25 int main() 26 { 27 while(cin>>n) 28 { 29 30 dp[1]=3; 31 dp[2]=9; 32 for(int i=3;i<=n;i++) 33 dp[i]=2*dp[i-1]+dp[i-2]; 34 cout<<dp[n]<<endl; 35 36 } 37 }