问题的原始链接在这里：https://code.google.com/codejam/contest/90101/dashboard#s=p2&a=2
简单地说，我们需要找出字符串s=“Welcome to code jam”作为给定字符串s的子序列出现的次数，例如。
s=“欢迎使用代码堵塞”
t=“wweellcommee到代码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到结束]
其中subseq（i，k）=t中s[i到end]的子序列的数目[k到end]
其中s（i）=第i个索引处的字符
式中T（k）=T中第k个索引处的字符
ans=子q（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结束]
结论：由于
a.>和b.>产生完全不同的子序列，因此要评估所有可能的子序列，我们需要评估它们的总和。2.>
else Subseq(i,k) = Subseq(i,k+1)
与case
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）&once
对于subseq（0,0），如果只计算一次subseq（1,2）并将其存储在
供以后使用的表。
所以dp建议我们预先计算当前继承权中低于的所有值
子问题在评估当前问题之前，这样我们就可以防止重复研究
相同子问题的计算。
因此在上面的例子中，我们可以评估Subseq（1,2）和Subseq（2,3）并将其存储在
二维表并在计算子集（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）的所有值的伪代码中，我们已经有了所需子问题的值
如果你没有得到上述任何解释，请评论
关于algorithm - Google Jam2009。C.欢迎使用Code Jam。无法理解动态编程，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19916527/