时间戳

首页 > 解决方案 > 如何在没有明显模式的情况下记忆或制作递归函数？

c++ - 如何在没有明显模式的情况下记忆或制作递归函数？

问题描述

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

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

前任。字符串“bac”，您首先将空字符串设为“a”，然后它可以是“ba”或“ab”，然后我们再试一次，我们根据最后的结果得到它现在可以是“ bac ” ”、“cba”、“abc”、“出租车”。我们知道这是可能的，所以我们返回 true。我们最多只能执行此过程 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;
        }
    }

}```

标签： c++performancerecursionmemoization

解决方案

  1. 你正在做蛮力方法，它的时间复杂度为n * 2^n. 在 20 左右时失败（TLE）看起来很合理n（考虑到t最多 10000）
  2. 我想不出一种有效记忆的方法，但是这个问题可以很容易地用贪婪的方法解决。您不必检查所有组合。看看官方社论

推荐阅读