问题原链接在这里: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 问题的分步过程以及它为何有效？

câu trả lời hay nhất

通俗的解释一下:

         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.> Và b.> 生成完全不同的子序列，因此要评估所有可能的子序列，我们需要评估它们的总和。

2.>

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

Và 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.>

sử dụng 5.> Và 4.> Và 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.>

sử dụng 6.> Và 2.> Và 1.>

Subseq(1,2) = 1

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

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

Tóm lại

Subseq(0,0) = 2 có nghĩa là S="abc" xuất hiện 2 lần dưới dạng dãy con khác biệt trong T = "aabc"

Bây giờ chúng ta đã biết cách giải quyết vấn đề, câu hỏi đặt ra là chúng ta có thể giải quyết nó nhanh hơn không?

Câu trả lời cho câu hỏi trên là lập trình động.

Như chúng ta có thể thấy trong ví dụ trên, chúng ta đã sử dụng Subseq(1,2) hai lần và một lần cho Subseq(1,1) & một lần

cho Subseq(0,0) vì vậy nếu chúng ta chỉ tính Subseq(1,2) một lần và lưu nó vào

Mẫu để sử dụng sau này.

Vì vậy DP đề nghị chúng ta tính toán trước tất cả các giá trị bên dưới giá trị hiện tại trong hệ thống phân cấp hiện tại

Đánh giá các bài toán con trước bài toán hiện tại, làm như vậy để tránh sự dư thừa

Tính toán cùng một bài toán con.

Vì vậy, trong ví dụ trên, trước tiên chúng ta có thể tính Subseq(1,2) & Subseq(2,3) và lưu trữ nó trong

Bảng hai chiều, được sử dụng trực tiếp khi tính Subseq(0,0)

Bây giờ câu hỏi đặt ra là các vấn đề phụ trong hệ thống phân cấp thấp nhất là gì?

Trong trường hợp này, chúng tôi lưu ý phương trình: -

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

or

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

Chúng ta có thể nhận thấy rõ ràng rằng mỗi bài toán (i,k) chỉ phụ thuộc vào (i,k+1) và (i+1,k+1)

Vậy cả i và k đều phụ thuộc vào giá trị lớn hơn hoặc bằng chính chúng.

Sử dụng quan sát trên, chúng ta có thể tính toán bảng 2D (i,k) bắt đầu từ các giá trị cao hơn

Mọi khả năng của i&j và mục nhập (0,0) sẽ là lời giải cho bài toán

mã giả:-

lenS = chiều dài(S)

lenT = chiều dài(T)

// Bảng lưu trữ số dãy con cho tất cả các bài toán con 

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

// Chuỗi rỗng là chuỗi con của chuỗi rỗng 

Subseq[lenS][lenT] = 1

// Chuỗi NoN-Emtpy không phải là chuỗi con của chuỗi trống

for(i = 0; i
   Subseq[i][lenT] = 0


// Chuỗi emtpy luôn là chuỗi con của chuỗi Không trống 

for(k = 0; k
   Subseq[lenS][k] = 1


// Đánh giá bảng từ giá trị cao hơn đến giá trị thấp hơn

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]

   khác Subseq[i][k] = Subseq[i][k+1]         


}



}

// Trả lời

in Subseq[0][0]

Để ý:

Trong mã giả ở trên cho tất cả các giá trị (i,k), chúng ta đã có sẵn các giá trị cho bài toán con bắt buộc

Nếu bạn không nhận được bất kỳ lời giải thích nào ở trên, vui lòng để lại nhận xét

Về thuật toán - Google Jam 2009. C. Chào mừng đến với Code Jam. Không hiểu lập trình động, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/19916527/