我正在解决这个问题-
给定一个由a、b和c组成的字符串，我们可以取任意两个相邻的不同的字符，并将其替换为第三个字符。对于例如，如果"a"one_answers"c"相邻，则可以将它们替换为"b"。什么是通过应用此操作可以得到的最小字符串反复地
现在，我已经编写了以下递归解决方案（效率很低），但希望将其转换为自上而下或自下而上的解决方案。
问题：我无法想出一个用于记忆的表格结构。尽管我必须只输出结果字符串的长度，但如何在不实际解决问题的情况下解决它。字符串正在减少，那么我该如何存储它们？
任何关于DP解决方案或Memoization的提示都将非常棒！
EDIT很多人都提出了自上而下的存储解决方案，请也尝试自下而上。
#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;
}
我有点太懒了，没有仔细考虑这个问题，但我会给你一种经常有效的记忆方法。
引入相互递归，而不是直接递归。
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。
这并不能解决问题，但我注意到：
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'将对字符串"bb"求值为true。这适用于具有相同值的任何连续字符串，例如"bb"、"cc"。
也许在这种情况下，您可以取两个连续字符的差，并检查它们是否为非零。
您可以通过将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;
}
无论我从这个问题中了解到什么，解决方案都应该是
输入的长度-如果所有输入字符都像一样
aaaaa - 5
bbb - 3
在其他情况下为1。
如果我遗漏了问题的某个部分，请纠正我。
绝对最小值为1。然而，字符串的细节和替换规则可以在1和n之间产生，其中n是字符串的长度。
对于特定的例子，最小的可能是n/2，因为你取2个字符并将它们替换为1（无法进一步替换），所以即使你有"acacacacacacacac"，这是最好的情况，你仍然只能实现2的缩减因子。
我在竞争性编程研讨会上解决了一个类似的问题，事实上，你提出的解决方案还不够快。
我的解决方案是创建这样的矢量：
string s;
cin >> s;
int length = s.length();
vector<vector<int> > v(length, vector<int>(length)); // 2d array of size length*length.
其中v[i][j]将是s的从i到j的子串可以达到的最小长度。
以后你所要做的就是把这个表填得越来越大。希望能有所帮助。
"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