动态规划问题解决交替字符串的方法

Question

我曾试图解决这个问题，但最终放弃了。后来我找到了下面的解决方案，虽然我不明白这个解决方案是如何工作的，也不知道为什么会有效。如果有更深入的解释，将不胜感激。

问题：

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given:

s1 = "aabcc"
s2 = "dbbca"

• When s3 = "aadbbcbcac", return true.
• When s3 = "aadbbbaccc", return false.

解决方案：

  public static boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0)
            return true;

        else if (s3.length() != s1.length() + s2.length())
            return false;
        boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];
        isInter[0][0] = true;
        for ( int i = 1; i <= s1.length(); ++i){
            if (s1.charAt(i-1) == s3.charAt(i-1))
                isInter[i][0] = true;
            else
                break;
        }
        for ( int i = 1; i <= s2.length(); ++i){
            if (s2.charAt(i-1) == s3.charAt(i-1))
                isInter[0][i] = true;
            else
                break;
        }
        // DP
        for ( int i = 1; i <= s1.length(); ++i){
            for ( int j = 1; j <= s2.length(); ++j){
                if (s3.charAt(i+j-1) == s1.charAt(i-1))
                    isInter[i][j] = isInter[i-1][j] || isInter[i][j];
                if (s3.charAt(i+j-1) == s2.charAt(j-1))
                    isInter[i][j] = isInter[i][j-1] || isInter[i][j];
            }
        }
        return isInter[s1.length()][s2.length()];
    }

- ShahrukhKhan

Answer 1

我在这里使用Python切片语法，因为它很方便。 S[:-1] 表示字符串 S 去掉最后一个字符，S[:n] 表示前缀长度为 n 的字符串 S。

关键思想是，如果 C 是 A 和 B 的交错字符串，则 C[:-1] 要么是 A 和 B[:-1] 的交错字符串，要么是 A[:-1] 和 B 的交错字符串。另一方面，如果 C 是 A 和 B 的交错字符串，则 C + 'X' 是 A + 'X' 和 B 的交错字符串，也是 A 和 B + 'X' 的交错字符串。

这些都是我们需要应用动态规划的子结构属性。

我们定义 f(i, j) = true，如果 s1[:i] 和 s2[:j] 可以交错形成 s3[:(i+j)]，否则 f(i,j) = false。根据上述观察，我们有：

f(0,0) = true
f(i,0) = f(i-1, 0) if s3[i-1] == s1[i-1]
f(0,j) = f(0, j-1) if s3[j-1] == s2[j-1]
f(i,j) = true if s3[i+j-1] = s1[i-1] and f(i-1, j)
f(i,j) = true if s3[i+j-1] = s2[j-1] and f(i, j-1)

在其他所有情况下，我们都有f(i,j)=false。Java代码只是使用动态规划实现了这个递归。话虽如此，我会用一种更简洁的方式来实现它：

for (int i = 0; i <= s1.length(); ++i)
    for (int j = 0; j <= s2.length(); ++j)
        isInter[i][j] = (i == 0 && j == 0)
           || (i > 0 && s1.charAt(i-1) == s3.charAt(i+j-1) && isInter[i-1][j])
           || (j > 0 && s2.charAt(j-1) == s3.charAt(i+j-1) && isInter[i][j-1]);

- Niklas B.

---

嗨，你能否修改你的答案以支持Java？我不理解Python字符串修改语法。 - ShahrukhKhan

@ShahrukhKhan：如果需要，您可以自己进行翻译：正如我所提到的，A[:n] = A.substring(0,n)和A[:-1] = A.substring(0,A.length-1)。我认为您遇到的主要问题是在概念层面上，因此伪代码应该足以帮助您理解。 - Niklas B.

@ShahrukhKhan 很遗憾，没有一种神奇的技巧可以让你更快地解决问题。但了解DP（最优子结构性质）背后的理论是有帮助的。对于思考方式，递归思考比迭代思考更为有效。在掌握基本知识的基础上，练习思考问题是学习的最佳途径。像TopCoder和Codeforces这样的平台有大量的资料可供学习。TopCoder教程在学习基础知识方面实际上是有些有用的（还有一篇关于DP的文章）。 - Niklas B.

我知道这是一个有点模糊的问题，但是你理解问题的能力给我留下了深刻印象，我很好奇你是通过什么方式进行练习的，是只做TopCoder和Codeforces吗？也许我认为一本书会有很好的例子等等。 - ShahrukhKhan

@ShahrukhKhan 对于这个问题，解决最长公共子序列和莱文斯坦距离的众所周知算法使用了相同的技术。熟悉许多不同的算法和问题绝对有帮助。不确定哪些书籍值得一看，我通常通过查看代码和研究材料来学习东西。我听说Knuth的书和Cormen都很不错。是的，竞争编程教给你很多关于算法的东西。 - Niklas B.

Answer 2

前几行代码只处理基于输入字符串长度的简单情况。通过这些测试，可以使剩余的代码更简单并且假设长度相等。该算法的核心是计算一个数组isInter，其中isInter[i][j]在迭代(i, j)后为true，当且仅当s3的前i+j个字符可以由s1的前i个字符与s2的前j个字符交错形成。isInter[i][0]为true当且仅当s3的前i个字符与s1的前i个字符匹配。同样，isInter[0][i]为true当且仅当s3的前i个字符与s2的前i个字符匹配。最终的循环使用已经计算好的元素和s3的下一个字符与s1的下一个字符或者s2的下一个字符之间的匹配来填充isInter的剩余元素。在完全计算完isInter之后，当且仅当整个s3可以由整个s1与整个s2交错形成时，isInter[s1.length()][s2.length()]为true。

- Patricia Shanahan

---

我认为这暴露了代码中的一个 bug -- if (s1.charAt(i-1) == s3.charAt(i-1)) 应该是 if (s1.charAt(i-1) == s3.charAt(i-1) && isInter[i-1][0])，同样适用于第二个基本情况循环。 - j_random_hacker

@j_random_hacker 我认为break语句有效地实现了那个规则。isInter的所有元素最初都是false。 - Patricia Shanahan

啊，原来是这样——问题出在我身上了！ - j_random_hacker

Answer 3

这里是另一种尝试展示代码如何工作的方式，使用极其简单的C++语法。代码中有一些内联注释供您理解。它再也不能更简单了 :)

//using dynamic programming : O(n^2)
bool is_interleaved_On2_DP(string s1, string s2, string s3)
    {
    bool ret = false;
    int len1 = s1.length();
    int len2 = s2.length();
    int len3 = s3.length();

    if( len1 + len2 != len3 )
        {
        return ret;
        }

#define M(i, j) match[ (i) * len1 + (j) ]

    //bool match[len1 + 1][len2 + 1]; //todo; use dynamic allocation
    bool* match = new bool[ (len1+1)*(len2+1) ];
    int i, j, k;

    /* init match table to be all false */
    for( i = 0; i <= len1; i++ )
        {
        for( j = 0; j <= len2; j++ )
            {
            M(i, j) = false;
            }
        }

    /* init match[0][0] == true */
    M(0, 0) = true; //why ? null is interleaving 2 other nulls :)

    /* init the s1 side of table i.e. column */
    for( i = 1; i <= len1; i++ )
        {
        char c1 = s1[i - 1];
        char c3 = s3[i - 1];
        if(c1 == c3)
            {
            M(i, 0) = true;
            }
        else
            {
            break;
            }
        }

    /* init the s2 side of table i.e. row */
    for( j = 1; j <= len2; j++ )
        {
        char c2 = s2[j - 1];
        char c3 = s3[j - 1];
        if(c2 == c3)
            {
            M(0, j) = true;
            }
        else
            {
            break;
            }
        }

    /* compute remaining table */
    for( i = 1; i <= len1; i++ )
        {
        char c1 = s1[i - 1];
        for( j = 1; j <= len2; j++ )
            {
            char c2 = s2[j - 1];
            int k = i + j; //index for s3
            char c3 = s3[k - 1];

            if(c1 == c3)
                {
                M(i, j) = M(i - 1, j) || M(i, j);
                }

            if(c2 == c3)
                {
                M(i, j) = M(i, j - 1) || M(i, j);
                }
            }
        }

    ret = M(len1, len2);

    delete [] match;
#undef M
    return ret;
    }

- Viren