我为群众办实事活动方案_乐清网络公司哪家好_游戏推广怎么做_网站建设详细方案模板

---

一、题目描述

「力扣 115. 不同的子序列」是一道经典的动态规划题，题目的描述如下：

给定一个字符串 s 和一个字符串 t，计算在 s 的子序列中 t 出现的个数。子序列表示通过删除 s 中的某些字符（可以是 0 个或者多个）得到的新字符串，且不改变字符的相对顺序。

示例:

输入：s = "rabbbit", t = "rabbit"
输出：3

二、解题思路

1. 问题分析

题目要求我们找出字符串 t 在字符串 s 的不同子序列中的出现次数。我们可以考虑用动态规划来解决这个问题。

首先，我们需要明确的是：

• 字符串 t 出现在字符串 s 的子序列中，意味着 t 的字符顺序必须和 s 中的某些字符相同，且这些字符不需要连续，但必须保持顺序一致。
• 我们需要求出有多少种方法可以通过删除 s 的某些字符使得剩下的字符恰好组成 t。

2. 动态规划的定义

为了进行状态转移，我们定义一个二维数组 dp[i][j]：

• dp[i][j] 表示使用 s[0:i] 的前 i 个字符，能够形成 t[0:j] 的前 j 个字符的子序列个数。

特别地：

• 当 j = 0 时，t 是空字符串，空字符串是所有字符串的子序列，因此对于任何 i，dp[i][0] = 1。
• 当 i = 0 且 j > 0 时，dp[0][j] = 0，因为空的 s 无法生成非空的 t。

3. 状态转移方程

我们可以通过遍历字符串 s 和 t 来填充 dp 表。具体的状态转移分为两种情况：

1. 如果 s[i-1] != t[j-1]，说明我们不能使用 s[i-1] 这个字符来匹配 t[j-1]，因此 dp[i][j] = dp[i-1][j]。
2. 如果 s[i-1] == t[j-1]，我们有两个选择：
   • 不使用 s[i-1] 来匹配 t[j-1]，此时 dp[i][j] = dp[i-1][j]。
   • 使用 s[i-1] 来匹配 t[j-1]，此时 dp[i][j] = dp[i-1][j-1]。

因此，当 s[i-1] == t[j-1] 时，状态转移方程为：
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

4. 边界条件

• dp[0][0] = 1 表示空的 s 和空的 t 是可以匹配的。
• dp[i][0] = 1 表示 t 为空时总是可以匹配任意的 s。

三、代码实现

下面是使用Go语言实现的具体代码：

package mainimport "fmt"// 不同的子序列
func numDistinct(s string, t string) int {m, n := len(s), len(t)// 初始化一个 (m+1) x (n+1) 的二维数组dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}// 边界条件：dp[i][0] = 1，表示空的 t 总是 s 的子序列for i := 0; i <= m; i++ {dp[i][0] = 1}// 填充 dp 数组for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if s[i-1] == t[j-1] {dp[i][j] = dp[i-1][j] + dp[i-1][j-1]} else {dp[i][j] = dp[i-1][j]}}}// 返回结果return dp[m][n]
}func main() {s := "rabbbit"t := "rabbit"fmt.Println(numDistinct(s, t)) // 输出 3
}

四、代码详解

1. 初始化二维数组 dp：
   我们创建一个二维数组 dp，大小为 (m+1) x (n+1)，其中 m 是字符串 s 的长度，n 是字符串 t 的长度。之所以要多加一行和一列，是为了处理边界情况，确保我们可以正确地填充 dp 表。

2. 设置边界条件：

   • dp[i][0] = 1，表示空的 t 始终是 s 的子序列。
   • dp[0][j] = 0，当 s 为空时，无法匹配非空的 t。

3. 填充 dp 表：

   • 当 s[i-1] == t[j-1] 时，表示我们有两种选择，既可以不使用 s[i-1] 来匹配，也可以使用。因此我们将两种情况的结果相加。
   • 当 s[i-1] != t[j-1] 时，说明 s[i-1] 无法参与匹配，这时结果只能是 dp[i-1][j]。

4. 返回结果：
   最终，dp[m][n] 就是我们所求的 t 在 s 中作为子序列出现的次数。

五、总结

本题的核心在于通过动态规划解决字符串的子序列问题。通过构造一个二维数组来记录每个子问题的解，并且通过合理的状态转移公式来进行递推，最终得到结果。这种解法的时间复杂度为 O(m * n)，空间复杂度也是 O(m * n)，适用于中等规模的输入。

通过这道题的练习，我们不仅巩固了动态规划的基础知识，还学会了如何在 Go 语言中高效地实现动态规划算法。

希望这篇文章对你有所帮助！如果你有其他问题或者想法，欢迎在评论区讨论！

---