5

我正在解决这个问题-

给定一个由 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;
}
4

7 回答 7

2

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

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

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

wherereduce_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.

于 2012-07-28T11:00:36.073 回答
1

您可以通过将结果存储reduce(s)在map<string,string>.

string reduce(string s, map<string,string>& memo) {
    if (memo.count(s)) {
        return memo[s];
    }
    // The rest of your code follows...
    memo[s] = min;
}
于 2012-07-28T11:02:22.333 回答
1

这并不能解决问题，但我注意到：

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;
}

根据问题陈述不起作用：

我们可以取任意两个 相邻的不同字符并将其替换为第三个字符。

考虑字符串s = "bb"。既不s[0]也不s[1]等于'a'，这意味着条件s[0] != 'a' && s[1] != 'a'将评估true为字符串"bb"。这适用于任何具有相同值的连续字符字符串，例如"bb"，"cc"。

也许在这种情况下，您可以取两个连续字符的差异，并检查它们是否非零。

于 2012-07-28T11:16:10.980 回答
0

无论我从问题中了解到什么，解决方案都应该是

输入的长度 - 如果所有输入字符都相同

aaaaa - 5
bbb - 3

在其他情况下为 1。

如果我错过了问题的某些部分，请纠正我。

于 2012-07-28T10:54:21.400 回答
0

绝对最小值是1。但是，字符串和替换规则的细节可能会在1和之间产生n，其中n是字符串的长度。

对于具体的例子，最小的可能是n/2，因为你取 2 个字符并用 1 替换它们（不能进一步替换），所以即使你有"acacacacacacacac"，最好的情况，你仍然只能实现 2 减少的因素。

于 2012-07-28T10:58:30.593 回答
0

我在竞争性编程研讨会上解决了一个类似的问题，确实你提出的解决方案不够快。

我的解决方案是创建这样的向量：

string s;
cin >> s;
int length = s.length();
vector<vector<int> > v(length, vector<int>(length)); // 2d array of size length*length.

wherev[i][j]将是子字符串 from ito jofs可以达到的最小长度。

稍后您所要做的就是将这张表填得越来越大。希望有帮助。

于 2012-07-28T11:15:42.833 回答
0 
"a...a" (“a" * n) == > n
"b...b" (“b" * n) == > n
"c...c" (“c" * n) == > n
 any other ==> 1 or 2 with my greedy algorithm.

如果我们在这个贪心算法中得到 2，我不能证明它是输入字符串的最小结果。

贪心算法

while the last two is the same character { // the number of the same characters
    find the last replaceable pair         // at the tail will decrease until
        reduce them                        // it become 1
}

while find the first replaceable pair
    reduce them
于 2012-07-28T11:58:57.610 回答