如何记忆或制作没有明显模式的递归函数？

Question

考虑以下代码，它是为 Codeforces Round #731 (Div. 3) 问题 B https://codeforces.com/contest/1547/problem/B

完成的

简而言之，给你一个字符串，你应该检查是否可以通过在开始为空的字符串的前后按字母顺序依次添加字母来创建该字符串。

例如。字符串“bac”，你首先要使空字符串为“a”，然后它可以是“ba”或“ab”，然后我们再试一次，我们根据最后的结果得到它现在可以是“bac", "cba", "abc", "cab"。我们知道这是可能的，所以我们 return 正确。我们最多只能执行此过程 26 次。

我的代码会做一棵树，抓取一个基本字符串作为头部，还有两个子节点，一个前面加字母，一个后面加字母，如果都不行，那我将对子节点再次重复。

我重写了我的解决方案并发送了一个完全不同的解决方案，但我仍然想知道是否有一种优化方法可以实际执行。如果 n 大约为 14 或 15，则代码有效，它会有点卡顿但可以完成；但是一旦达到 20，它甚至不会完成。

#include <iostream>
#include <string>

using namespace std;


bool solve(string fs,string s = "", int n = 0){
    if(s == fs){
        return true;
    }
    if(n > 26 || s.size() > fs.size()){
        return false;
    }
    if(solve(fs,s+(char)(96+n+1),n+1) ||solve(fs,(char)(96+n+1)+s,n+1)){
        return true;
    }
    return false;
}

int main(){
    int t;cin>>t;
    for(int i = 0; i < t; i++){
        string p;
        cin>>p;
        if(solve(p)){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }

}```

Answer 1

您正在使用蛮力方法，其时间复杂度为 n * 2^n。当 n 大约为 20 时（考虑到 t 高达 10000）
我想不出一种有效的记忆方法，但是这个问题可以用贪心的方法轻松解决。您不必检查所有组合。 Check out the official editorial

如何记忆或制作没有明显模式的递归函数？

How to memoize or make recursive function with no apparent pattern?

c++

performance

recursion

memoization