問題の元のリンクは次のとおりです: https://code.google.com/codejam/contest/90101/dashboard#s=p2&a=2
簡単に言えば、文字列 S="welcome to code jam" が指定された文字列 S のサブシーケンスとして何回出現するかを調べる必要があります。たとえば、 S="welcome to code jam" T="wweellccoommee to code qps jam" などです。
理論はわかるが実際のDPは苦手。このDPの問題を解決するための段階的なプロセスと、それが機能する理由を説明してください。
簡単に説明すると：
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 to end] を示します。
Subseq(i,k) = T[k to end] 内の S[i to end] のサブシーケンスの数
ここで、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 は、T[k to end] 内の S[i to end] のサブシーケンスの一部である可能性があります
したがって、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"
これで、問題を解決する方法がわかりました。問題は、より速く実行できるかということです。
上記の質問に対する答えは Dynamic Programming です。
上記の例で見たように、Subseq(1,1) に 1 回、Subseq(1,2) を 2 回使用しました。
Subseq(0,0) の場合、Subseq(1,2) を 1 回だけ計算して格納すると便利です。
後で使用するためのテーブル。
したがって、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 の両方が、それ自体より大きいか等しい値に依存します。
上記の観測を使用して、より高い値から開始して 2 次元テーブル (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) のすべての値に対する上記の擬似コードでは、必要なサブ問題の値が既にあります。
上記の説明のいずれかが得られない場合はコメントしてください
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]
上記はコードが行っていることです
ちゃんと気がつけば私のやり方と同じですが、文字列の順番が逆です