algorithm - 将不同的事件计数为子序列

Question

我正在研究 geeksforgeeks 的“将不同的事件计数为子序列问题”。我想了解“其他”情况。在最后一个字符匹配的情况下，为什么没有来自 S + 的最后一个字符的结果没有来自 S 和 T 的最后两个字符？

Input  : S = banana, T = ban
Output : 3
T appears in S as below three subsequences.
[ban], [ba  n], [b   an]

// Returns count of subsequences of S that match T 
// m is length of T and n is length of S
subsequenceCount(S, T, n, m)

//空字符串是所有的子序列。 1) 如果T的长度为0，则返回1。

//否则没有字符串可以是空 S 的序列。 2) 否则如果 S 为空，则返回 0。

3) 否则如果 S 和 T 的最后一个字符不匹配， 删除 S 的最后一个字符并重复剩余 返回子序列计数(S, T, n-1, m)

4) Else(Last characters match)，结果为sum 两个计数。

    // Remove last character of S and recur.
    a) subsequenceCount(S, T, n-1, m) + 

    // Remove last characters of S and T, and recur.
    b) subsequenceCount(S, T, n-1, m-1)  

Answer 1

考虑 S="banan" 和 T="ban" 的情况。最后的字符匹配，因此在 S 的子序列中出现的任何 T 必须:

• 不包括 S 的最后一个字符。这简化为子问题 S="bana"，T="ban"，出现 1 次:“bana”。<
• 包括 S 的最后一个字符。这简化为子问题 S="bana", T="ba"。这里出现了 2 次:“bana”和“bana”。如果我们回到主要问题，相应的出现是“banan”和“banan” >”。

出现的总次数是两个子问题的总和。