解决"减少弦乐"的挑战

Question

我已经看到各种讨论和代码尝试解决来自interviewstreet.com 的"字符串缩减"问题,但他们都没有通过动态编程来解决它.

在动态编程部分列出,问题描述如下:

给定由a,b和c组成的字符串,我们可以执行以下操作:获取任意两个相邻的不同字符,并将其替换为第三个字符.例如,如果'a'和'c'相邻,则可以用'b'代替.

重复应用此操作可以产生的最小字符串是多少？

可以使用详尽的强力搜索来解决问题,有效地创建所有可能替换的树:

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

对于large N(N <= 100)来说,这显然是失败的,所以我试图把它分解成更小的子问题,记住它们,并合并结果.

问题在于我无法确定应用动态编程所需的具有"最佳子结构"的状态(或者换言之,"合并"子问题的结果).最小化字符串的一部分并不能保证最终的字符串确实是最小的解决方案.

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

Answer 1

使这个问题变得棘手的是，您需要将其视为连续的两个动态规划问题。

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

第二个给出了你的答案。如果您已经解决了第一个问题，那就更简单了。