115. 不同的子序列

题目描述

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit**

示例 2：

输入：s = “babgbag”, t = “bag”
输出：5

提示：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

解法一：动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func numDistinct(s string, t string) int {
    h, w := len(s), len(t)
    if h < w {
        return 0
    }
    dp := make([][]int, h+1)
    for i := 0; i < h+1; i++ {
        dp[i] = make([]int, w+1)
        dp[i][w] = 1
    }
    for i := h - 1; i >= 0; i-- {
        for j := w - 1; j >= 0; j-- {
            if s[i] == t[j] {
                dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
            } else {
                dp[i][j] = dp[i+1][j]
            }
        }
    }

    return dp[0][0]
}