algorithm - Google Jam 2009。C. 欢迎来到 Code Jam。看不懂动态规划

Question

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

简单来说，我们需要找出字符串 S="welcome to code jam"作为给定字符串 S 的子序列出现了多少次，例如S="欢迎来到代码挑战赛"T="wweellccoommee 编码 qps jam"

我知道理论，但在实践中不擅长 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 表示子字符串 S[i to end]

其中k表示子串T[k到结尾]

其中 Subseq(i,k) = T[k 到结束] 中 S[i 到结束] 的子序列数

其中 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) 那么

一个。>

索引 k 可能是 T[k 到结束] 中 S[i 到结束] 的子序列的一部分

因此，T[k to end] 中 S[i to end] 的以 k 开始的子序列数将等于 T[k+1 to end] 中 S[i+1 to end] 的子序列数

b.>

子序列可能不以 k 开头，在这种情况下我们需要评估 S[i 以结束]T[j+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.>

我=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.>

我 = 1

k = 1

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

如您所见，Subseq(1,2) 用于两个派生方程，因此我将只计算一次

3.>

我 = 1

k = 2

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

4.>

我 = 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.>

我 = 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 建议我们预先计算当前层次结构中低于当前值的所有值

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

相同子问题的计算。

因此在上面的例子中，我们可以先计算 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) 值的伪代码中，我们已经有了所需子问题的值

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