问题的原始链接在这里：https ://code.google.com/codejam/contest/90101/dashboard#s=p2&a=2
简单来说，我们需要找出字符串 S="welcome to code jam" 出现多少次作为给定字符串 S 的子序列，例如 S="welcome to code jam" T="wweellccommee to code qps jam"
我知道理论，但在实践中不擅长 DP。您能否通过示例解释解决此 DP 问题的分步过程以及它为什么有效？
问问题
918 次
3 回答
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 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) 那么
一个。>
索引 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 开头，我们需要在 T[j+1 to end] 中评估 S[i to end]
结论：由于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) 的所有值的伪代码中，我们已经有了所需子问题的值
如果您没有得到上述任何解释，请发表评论
于 2013-11-12T07:19:28.680 回答
0
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]
以上是代码在做什么
如果你注意到它与我的方法相同，但字符串的顺序相反
于 2013-11-12T12:00:32.487 回答
0
我在java中找到了另一个更容易的解决方案。我们一次在字符串 S 1 char 中向后移动。在此特定示例中，DP-array 传递以下状态： 100(initially)->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]);
于 2013-11-12T10:21:36.130 回答