Google Jam 2009年。C.欢迎来到Code Jam。无法理解动态编程

Question

这个问题的原始链接在这里：https://code.google.com/codejam/contest/90101/dashboard#s=p2&a=2

简单地说，我们需要找出字符串S=“欢迎使用code”作为给定字符串S的子序列出现了多少次，例如S=“欢迎使用code”T="wweellccoommee to code qps“。

我对理论有所了解，但在实践中并不擅长DP。你能用例子一步一步地解释解决这个DP问题的过程吗?为什么它是有效的？

Answer 1

简单地解释一下：

         if(S(i) == T(k))

           Subseq(i,k) = Subseq(i+1,k+1) + Subseq(i,k+1)

         else Subseq(i,k) = Subseq(i,k+1)

其中i表示结束的子串Si

其中k表示要结束的子串Tk

其中Subseq(i，k) =以Tk结束的Si的子序列数

其中S(i) =S中第i个索引处的字符

其中T(k) =T中第k个索引处的字符

Ans = Subseq(0,0)

解释：-

1.>

  if(S(i) == T(k))

           Subseq(i,k) = Subseq(i+1,k+1) + Subseq(i,k+1)

如果S(i) == T(k)，则

a.>

索引k可以是以Tk结束的Si的子序列的一部分

因此，在Tk到end中以Si开始的子序列的数量将等于在Tk+1到end中结束的Si+1的子序列的数量

b.>

子序列可能不是以k开头，在这种情况下，我们需要评估Si以Tj+1结尾

结论:由于a.>和b.>生成完全不同的子序列，因此要计算所有可能的子序列，我们需要计算它们的总和。

2.>

else Subseq(i,k) = Subseq(i,k+1)

与这里的情况1.>相反，a.>是不可能的，因为S(i) != T(k)，所以没有子序列可以以k开始，因此我们只剩下b.>作为可能性。

示例：-

S = "abc"  T = "aabc"

我们必须计算Subseq(0,0)

从上面的公式：

1.>

I=0

K=0

if(S(0)==T(0)) = true => Subseq(0,0) = Subseq(1,1) + Subseq(1,2)

现在我们需要Subseq(1,1) & Subseq(1,2)

2.>

I=1

K=1

if(S(1)==T(1)) = false => Subseq(1,1) = Subseq(1,2)

正如你所看到的，Subseq(1,2)在两个派生方程中都使用了，所以我只对它求值一次

3.>

I=1

K=2

if(S(1)==T(2)) = true => Subseq(1,2) = Subseq(2,3) + Subseq(1,3)

4.>

I=1

K=3

if(S(1)==T(3)) = false => Subseq(1,3) = Subseq(1,4)


as we know T(4) = null hence Subseq(1,4) = 0   hence Subseq(1,3) = 0

5.>

I=2

K=3

 if(S(2)==T(3)) = true => Subseq(2,3) = Subseq(3,4) + Subseq(2,4)


    Subseq(3,4) = 1 as S(3) = null & S(4) == null and null string is always subsequence of null string

    Subseq(2,4) = 0 as T[end] = null & S[2 to end] ! = null so S[2 to end] is not subsequence of T[end]

    Subseq(2,3) = 1 + 0 = 1

6.>

使用5.>、4.>和3.>

Subseq(2,3) = 1

Subseq(1,3) = 0

Subseq(1,2) = Subseq(2,3) + Subseq(1,3)

Subseq(1,2) = 1 + 0 = 1

7.>

使用6.>、2.>和1.>

Subseq(1,2) = 1

Subseq(1,1) = Subseq(1,2) = 1

Subseq(0,0) = Subseq(1,1) + Subseq(1,2) = 2

结论

Subseq(0,0) = 2 which means S="abc" appears 2 times as distinct subsequence in T = "aabc"

现在我们知道如何解决问题了，问题是我们能更快地解决这个问题吗？

上述问题的答案是动态规划。

正如我们在上面的例子中看到的，我们使用Subseq(1,2)两次，一次用于Subseq(1,1) &一次

对于Subseq(0,0)，如果我们只计算Subseq(1,2)一次并将其存储在

表，以供以后使用。

因此DP建议我们预先计算所有低于current层次结构的值

子问题在评估当前问题之前，这样做可以防止冗余

相同子问题的计算。

因此，在上面的示例中，我们可以在计算Subseq(1,2)和Subseq(2,3)之前将其存储在

二维表，在计算Subseq(0,0)时直接使用

现在问题来了，在最低的世袭制度中，哪些是子问题？

在这种情况下，我们注意到方程：

Subseq(i,k) = Subseq(i+1,k+1) + Subseq(i,k+1)

or

Subseq(i,k) = Subseq(i,k+1)

我们可以清楚地注意到，每个问题(i，k)只依赖于(i，k+1)和(i+1，k+1)

所以i和k都依赖于大于或等于它们自己的值。

使用上面的观察值，我们可以从更高的值开始计算二维表格(i，k)

I&j的所有可能性，条目(0,0)将是问题的解决方案

伪码：-

lenS = length(S)

lenT = length(T)

// Table to store subsequence count for all sub-problems 

Subseq[lenS+1][lenT+1];

// Empty string is subseq of Empty string 

Subseq[lenS][lenT] = 1

// NoN-Emtpy string is not subsequence of empty string

for(i = 0 ; i<lenS ; i++)
   Subseq[i][lenT] = 0


// Emtpy string is always subsequence of Non-empty string 

for(k = 0 ; k<lenT ; k++)
   Subseq[lenS][k] = 1


// Evaluate table from higher values to lower values

for(i = lenS-1 ; i>=0 ; i--) {


for(k = lenT-1 ; k>=0 ; k--) {



   if(S[i]==T[k]) 
       Subseq[i][k] = Subseq[i+1][k+1] + Subseq[i][k+1]

   else Subseq[i][k] = Subseq[i][k+1]         


}



}

// Answer

print Subseq[0][0]

备注：

在上面的伪代码中，对于(i，k)的所有值，我们已经有了所需的子问题的值

如果您没有得到上述任何解释，请评论

Answer 2

我在java中找到了另一个更简单的解决方案。我们在字符串S中一次向后移动1个字符。在这个特定的例子中，DP数组传递了以下状态:100(初始)->110->120->122->124，其中4是答案，但我也不理解这个解决方案：

    char[] T = "AABB".toCharArray();
    char[] S = "AB".toCharArray();

    int[] d = new int[S.length + 1];
    d[0] = 1;

    for (char c : T) {
        for (int i = S.length - 1; i >= 0; i--) {
            if (c == S[i]) {
                d[i + 1] += d[i];
            }
        }
    }

    System.out.println(d[S.length]);

Answer 3

java实现是解决这个问题的另一种方法，实际上更节省空间，这让我感到惊讶。

解释：-

d[i][k] = no of subsequence of S[0 to i] in T[0 to k]

d[i-1][k] = no of subsequnce of S[0 to i-1] in T[0 to k]

if(S[i]==T[k])
   d[i][k] = d[i][k-1] + d[i-1][k-1]

else d[i][k] = d[i][k-1]

以上就是代码正在做的事情

如果你注意到了，它和我的方法是一样的，但是和字符串的顺序相反