如何将递归解决方案转换为自下而上或自上而下的解决方案？

Question

我正在解决这个问题-

给定一个由 a、b 和 c 组成的字符串，我们可以取任意两个相邻的不同字符并将其替换为第三个字符。例如，如果 'a' 和 'c' 相邻，则可以将它们替换为 'b'。重复应用此操作可以产生的最小字符串是什么？

现在我已经编写了以下递归解决方案（远非有效），但想将其转换为自上而下或自下而上的解决方案。

问题：我无法提出用于记忆的表格结构。即使我只需要输出结果字符串的长度，我如何在不实际解决问题的情况下解决它。字符串越来越少，那么我如何存储它们？

任何关于 DP 解决方案或记忆的提示都会很棒！

编辑很多人提出了自上而下的记忆解决方案，请尝试自下而上。

#include <iostream>
#include <string>

using namespace std;

string reduce(string s)
{
    if (s.length() <= 1)
        return s;

    int k;
    char c = s[0];
    string min = s;
    for (k = 1; k < s.length() && c; ++k)
        if (s[k] != c)
            c = 0;
    if (c)
        return s;

    if (s.length() == 2){
        if (s[0] != 'a' && s[1] != 'a')
            s[0] = 'a';
        else if (s[0] != 'b' && s[1] != 'b')
            s[0] = 'b';
        else if (s[0] != 'c' && s[1] != 'c')
            s[0] = 'c';
        s.resize(1);
        return s;
    }

    for (k = 1; k < s.length(); ++k){
        string s1 = reduce(s.substr(0, k));
        string s2 = reduce(s.substr(k));

        if (s1.length() + s2.length() < min.length())
            min = s1 + s2;
        if (!s1.empty() && !s2.empty() && s1.back() != s2.front()){
            if (s1.back() != 'a' && s2.front() != 'a')
                s1.back() = 'a';
            else if (s1.back() != 'b' && s2.front() != 'b')
                s1.back() = 'b';
            else if (s1.back() != 'c' && s2.front() != 'c')
                s1.back() = 'c';
            s1 = reduce(s1 + s2.substr(1));
            if (s1.length() < min.length())
                min = s1;
        }

    }
    return min;
}

int main()
{
    string input;
    cin >> input;
    cout << reduce(input) << endl;
    return 0;
}

Answer 1

我有点懒得想清楚这个问题，但我会给你一种通常足够有效的记忆方法。

不直接递归，而是引入相互递归。

std::string reduce(std::string const &s)
{
    // ...
    string s1 = reduce_memo(s.substr(0, k));
    string s2 = reduce_memo(s.substr(k));
    // ...
}

其中reduce_memo维护一个哈希表，即unordered_map，将子问题映射到它们的解决方案。

// static is incredibly ugly, but I'll use it here for simplicity
static std::unordered_map<std::string, std::string> memo;

std::string reduce_memo(std::string const &s)
{
    try {
        return memo.at(s);
    } except (std::out_of_range const &) {
        std::string r = reduce(s);
        memo[s] = r;
        return r;
    }
}

在 C++98 中编程时，请std::map使用unordered_map.