输入一个整数n，表示字符串长度(1 ≤ n ≤ 30)
输出一个整数表示有多少个暗黑字符串
2 3
9 21
思路：这是一个动态规划问题，关键是推导出状态转移方程：dp[i]=2*dp[i-1]+dp[i-2]
#include<iostream> using namespace std; long long black_ans(int n){ long long dp[30]; dp[0]=3; dp[1]=9; dp[2]=21; for(int i=3;i<n;++i){ dp[i]=2*dp[i-1]+dp[i-2]; } return dp[n-1]; } int main(){ int n; while(cin>>n){ long long res=black_ans(n); cout<<res<<endl; } return 0; }
原文：http://www.cnblogs.com/rgly/p/7471452.html
