algorithm - 解决 "string reduction"挑战

Question

我已经看到各种讨论和代码尝试来解决 "String reduction"来自 interviewstreet.com 的问题，但没有一个是通过动态规划来解决的。

在 Dynamic Programming 下列出部分，问题描述如下:

Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'.

What is the smallest string which can result by applying this operation repeatedly?

这个问题可以使用穷举式暴力搜索来解决，有效地创建一个包含所有可能替换的树:

// this is more or less pseudo code from my head
int GetMinLength(string s)
{
    // solve edge cases
    if (s.Length == 1) return 1;
    if (s.Length == 2) return ReduceIfPossible(s);

    // recursive brute force
    int min = s.Length;
    for (int i = 0; i<s.Length-1; i++)
    {
        if (s[i] != s[i+1])
        {
            var next = GetMinLength(
                  s.Substring(0, i) + 
                  Reduce(s[i], s[i + 1]) +
                  s.Substring(i + 2)
                  );

            if (next < min) min = next;
        }
    }
}

这对于更大的 N 显然是失败的( N <= 100 )，所以我试图将它分解成更小的子问题，记住它们，然后合并结果。

问题是我无法确定 "optimal substructure" 的状态，需要应用动态规划(或换句话说“合并”子问题的结果)。最小化字符串的一部分并不能保证最终的字符串确实是最小的解决方案。

在这种情况下，可以合并到最终解决方案的子问题“状态”是什么？

Answer 1

之所以棘手，是因为您需要将其视为连续的 2 个动态规划问题。

1. 根据您最终得到的字符、开始位置、所有可能的结束位置建立一个表格，这些位置是一个可以简化为该字符的 block 。
2. 字符串的最后i 个字符可以减少到的最小长度。 (您在步骤 1 中构建的表可用于递归地将此问题简化为已解决的子问题。)

第二个提供您的答案。如果您已经解决了第一个问题，那就简单多了。