2021-08-14：給定兩個字符串S和T，返回S的所有子序列中有多少個子序列的字面值等于T。

福大大 答案2021-08-14：

樣本對應模型。

時間復雜度：O(N^2)。

空間復雜度：O(N^2)。

代碼用golang編寫。代碼如下：

package mainimport "fmt"func main() {    s := "1122"    t := "12"    ret := numDistinct1(s, t)    fmt.Println(ret)}func numDistinct1(S string, T string) int {    return process(S, T, len(S), len(T))}func process(s string, t string, i int, j int) int {    if j == 0 {        return 1    }    if i == 0 {        return 0    }    res := process(s, t, i-1, j)    if s[i-1] == t[j-1] {        res += process(s, t, i-1, j-1)    }    return res}

執行結果如下：

***

[左神java代碼](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class17/Code04_DistinctSubseq.java)