我的带记忆的动态编程算法有什么问题？

Question

*抱歉我的英语不好。如果有什么不明白的，请告诉我，这样我可以给你更多的信息'make sence'。

**这是第一次在 Whosebug 提问。我在这里搜索了一些正确提问的规则，但应该有一些我遗漏的东西。我欢迎所有反馈。

我目前正在解决算法题来提高自己的技能，我在一个问题上挣扎了三天。这个问题来自 https://algospot.com/judge/problem/read/RESTORE ，但是因为这个页面是韩文的，所以我试着把它翻译成英文。

问题
如果给定 'k' 条部分字符串，计算包含所有部分字符串的最短字符串。所有字符串仅包含小写字母。如果满足所有条件且长度相同的结果字符串超过1个，则选择任意字符串。

输入
在输入的第一行，给出了测试用例的数量'C'(C<=50)。对于每个测试用例，第一行给出部分字符串的数量 'k'(1<=k<=15)，接下来的 k 行给出部分字符串。部分字符串的长度在 1 到 40 之间。

输出
对于每个测试用例，打印包含所有部分字符串的最短字符串。

示例输入
3
3
地理
王子
静
2
世界
你好
3
胡言乱语
卡达布拉
dabr

示例输出
地理
你好世界
卡达布拉克

这是我的代码。我的代码似乎与示例输入完美配合，当我为自己进行测试输入并进行测试时，一切正常。但是当我提交这个代码时，他们说我的代码是'wrong'。

请告诉我我的代码有什么问题。您不需要告诉我整个固定代码，我只需要导致我的代码出错的示例输入。添加了代码说明，使我的代码更容易理解。

代码说明

将所有输入的部分字符串保存在向量“stringParts”中。
将当前最短字符串结果保存在全局变量“answer”中。
使用 'cache' 数组进行记忆 - 跳过重复的函数调用。

我设计的解决这个问题的算法分为两个函数—— restore() 和 eraseOverlapped().

restore() 函数计算包含 'stringParts'.
中所有部分字符串的最短字符串 resotre() 的结果保存在“answer”中。

对于 restore()，有三个参数 - 'curString'、'selected' 和 'last '.
'curString'代表当前选中的重叠字符串结果
'selected'代表'stringParts'当前选中的元素。使用位掩码使我的算法简洁。
'last'代表'stringParts'最后选择的元素，用于制作'curString'.

eraseOverlapped() 函数进行预处理 - 它会删除 'stringParts' 中可以在执行 restore() 之前完全包含到其他元素中的元素。

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#define MAX 15
using namespace std;

int k;
string answer; // save shortest result string

vector<string> stringParts;
bool cache[MAX + 1][(1 << MAX) + 1]; //[last selected string][set of selected strings in Bitmask]

void restore(string curString, int selected=0, int last=0) {
    //base case 1
    if (selected == (1 << k) - 1) {
        if (answer.empty() || curString.length() < answer.length()) 
            answer = curString;
        return;
    }
    //base case 2 - memoization
    bool& ret = cache[last][selected];
    if (ret != false) return;

    for (int next = 0; next < k; next++) {
        string checkStr = stringParts[next];
        if (selected & (1 << next)) continue;

        if (curString.empty())
            restore(checkStr, selected + (1 << next), next + 1);
        else {
            int check = false;
            //count max overlapping area of two strings and overlap two strings.
            for (int i = (checkStr.length() > curString.length() ? curString.length() : checkStr.length())
                ; i > 0; i--) {
                if (curString.substr(curString.size()-i, i) == checkStr.substr(0, i)) {
                    restore(curString + checkStr.substr(i, checkStr.length()-i), selected + (1 << next), next + 1);
                    check = true;
                    break;
                }
            }
            if (!check) { // if there aren't any overlapping area
                restore(curString + checkStr, selected + (1 << next), next + 1);
            }
        }
    }
    ret = true;
}
//check if there are strings that can be completely included by other strings, and delete that string.
void eraseOverlapped() {
    //arranging string vector in ascending order of string length
    int vectorLen = stringParts.size();
    for (int i = 0; i < vectorLen - 1; i++) {
        for (int j = i + 1; j < vectorLen; j++) {
            if (stringParts[i].length() < stringParts[j].length()) {
                string temp = stringParts[i];
                stringParts[i] = stringParts[j];
                stringParts[j] = temp;
            }
        }
    }

    //deleting included strings
    vector<string>::iterator iter;
    for (int i = 0; i < vectorLen-1; i++) {
        for (int j = i + 1; j < vectorLen; j++) {
            if (stringParts[i].find(stringParts[j]) != string::npos) {
                iter = stringParts.begin() + j;
                stringParts.erase(iter);
                j--;
                vectorLen--;
            }
        }
    }
}

int main(void) {
    int C;
    cin >> C; // testcase
    for (int testCase = 0; testCase < C; testCase++) {
        cin >> k; // number of partial strings
        memset(cache, false, sizeof(cache)); // initializing cache to false
        string inputStr;
        for (int i = 0; i < k; i++) {
            cin >> inputStr;
            stringParts.push_back(inputStr);
        }
        eraseOverlapped();
        k = stringParts.size();

        restore("");
        cout << answer << endl;
        answer.clear();
        stringParts.clear();
    }
}

Answer 1

在确定哪些 string-parts 可以从列表中删除后，因为它们包含在其他 string-parts 中，对此问题建模的一种方法可能是“taxicab ripoff problem”问题（或 Max TSP），其中每个可能因重叠而减少的长度都被赋予正权重。考虑到问题中的输入量非常小，他们似乎期望接近 brute-force 的解决方案，可能带有一些启发式和回溯或其他形式的记忆。

Answer 2

感谢所有试图帮助我解决这个问题的人。我实际上解决了这个问题，对我以前的算法做了一些改动。这些是主要变化。

在我之前的算法中，我将 restore() 的结果保存在全局变量 'answer' 中，因为 restore() 没有 return 任何东西，但是在自 restore() returns mid-process 答案字符串以来的新算法我不再需要使用 'answer'.
使用字符串类型缓存而不是布尔类型缓存。我发现在这个算法中使用 bool 缓存进行记忆是没有用的。
从 restore() 中删除了 'curString' 参数。由于我们在递归调用时只需要一个之前选择的部分字符串，所以'last'可以代替'curString'的作用。

代码

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#define MAX 15
using namespace std;

int k;

vector<string> stringParts;
string cache[MAX + 1][(1 << MAX) + 1];

string restore(int selected = 0, int last = -1) {
    if (selected == (1 << k) - 1) {
        return stringParts[last];
    }

    if (last == -1) {
        string ret = "";
        for (int next = 0; next < k; next++) {
            string resultStr = restore(selected + (1 << next), next);
            if (ret.empty() || ret.length() > resultStr.length())
                ret = resultStr;
        }
        return ret;
    }

    string& ret = cache[last][selected];
    if (!ret.empty()) {
        cout << "cache used in [" << last << "][" << selected << "]" << endl;
        return ret;
    }

    string curString = stringParts[last];
    for (int next = 0; next < k; next++) {
        if (selected & (1 << next)) continue;

        string checkStr = restore(selected + (1 << next), next);
        int check = false;
        string resultStr;
        for (int i = (checkStr.length() > curString.length() ? curString.length() : checkStr.length())
            ; i > 0; i--) {
            if (curString.substr(curString.size() - i, i) == checkStr.substr(0, i)) {
                resultStr = curString + checkStr.substr(i, checkStr.length() - i);
                check = true;
                break;
            }
        }
        if (!check)
            resultStr = curString + checkStr;

        if (ret.empty() || ret.length() > resultStr.length())
            ret = resultStr;
    }
    return ret;
}

void EraseOverlapped() {
    int vectorLen = stringParts.size();
    for (int i = 0; i < vectorLen - 1; i++) {
        for (int j = i + 1; j < vectorLen; j++) {
            if (stringParts[i].length() < stringParts[j].length()) {
                string temp = stringParts[i];
                stringParts[i] = stringParts[j];
                stringParts[j] = temp;
            }
        }
    }

    vector<string>::iterator iter;
    for (int i = 0; i < vectorLen - 1; i++) {
        for (int j = i + 1; j < vectorLen; j++) {
            if (stringParts[i].find(stringParts[j]) != string::npos) {
                iter = stringParts.begin() + j;
                stringParts.erase(iter);
                j--;
                vectorLen--;
            }
        }
    }
}

int main(void) {
    int C;
    cin >> C;
    for (int testCase = 0; testCase < C; testCase++) {
        cin >> k;
        for (int i = 0; i < MAX + 1; i++) {
            for (int j = 0; j < (1 << MAX) + 1; j++)
                cache[i][j] = "";
        }
        string inputStr;
        for (int i = 0; i < k; i++) {
            cin >> inputStr;
            stringParts.push_back(inputStr);
        }
        EraseOverlapped();
        k = stringParts.size();
        string resultStr = restore();
        cout << resultStr << endl;
        stringParts.clear();
    }
}

这个算法比我正在学习的书上建议的 'ideal' 算法慢很多，但它足够快，可以通过这道题的时间限制。

我的带记忆的动态编程算法有什么问题？

What's wrong with my dynamic programming algorithm with memoization?

c++

algorithm

memoization

dynamic-programming