FJ的字符串 （C++代码）--递归两行代码 --- 简短易理解---

解题思路:

FJ在沙盘上写了这样一些字符串： 

A1  =  “A” 

A2  =  “ABA” 

A3  =  “ABACABA” 

A4  =  “ABACABADABACABA” 

…  … 

你能找出其中的规律并写所有的数列AN吗？    

    根据规律可以看出 A（n）=A(n-1)+char(n+'A'-1) +A(n-1);

    所以这道题用递归在合适不过了，当然也可以用递推式；

注意事项:
    递归时写成 return f(n-1)+(char)('A'+n-1)+f(n-1)每一次会将f（n-1）计算两次，时间复杂度2^n次方，所以要只计算一次f（n-1）然后保存下来才行；

参考代码:

......
string s;int x;

string f(int n){
    if(n==1)return "A";
    return (s=f(n-1))+(char)('A'+n-1)+s;
}

int main() {
    cin>>x;
    cout<<f(x);
}