题目
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是。
示例
示例 1：
输入：s = “abc”
输出：7
解释：7 个不同的子序列分别是 “a”, “b”, “c”, “ab”, “ac”, “bc”, 以及"abc"。
示例 2：
输入：s = “aba”
输出：6
解释：6 个不同的子序列分别是 “a”, “b”, “ab”, “ba”, “aa” 以及 “aba”。
示例 3：
输入：s = “aaa”
输出：3
解释：3 个不同的子序列分别是 “a”, “aa” 以及 “aaa”。
提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成、
思路
1、首先想的就是DFS+set去重，但是超时了，然后去看的官方题解，学习了动态规划的做法
2、动态规划：
dp[i]的含义为以s[i]为结尾的子序列的数量和，这里状态转移方程可分为两步：
1.如果子序列中只含有s[i]这一个字符，那么只有一种情况
2.若如果子序列中包含至少两个字符，我们可以按照子序列的前一位来转移状态，可以枚举子序列的前一位的所有可能结果然后相加，即f[i]=f[0]+f[1]+⋯f[i−1]。
但是这样做肯定会有重复，如ab，abcb这种情况。
所以我们只需要加上最后出现某元素的子序列和即可。
由于题目中s中字符都是小写字符，我们可以设置一个长度为26的数组last，来记录每一个字母最后出现的下标，在进行累加操作时，只加上这些下标的序列和即可。
最后不要忘了每操作一个s中的下标，都要修改last数组中该下标对应字母的最后出现位置。
题解
1、菜鸟dfs+set去重做法
class Solution: def distinctSubseqII(self, s: str) -> int: ans = set() def process(n, index, s, tmp): if len(tmp) == n: ans.add(tmp) return for i in range(index, len(s)): tmp += s[i] process(n, i+1, s, tmp) tmp = tmp[:-1] for i in range(1, len(s)+1): process(i, 0, s, '') return len(ans) % (10 **9 + 7)
2、动态规划解法
class Solution: def distinctSubseqII(self, s: str) -> int: mod = 10 ** 9 + 7 n = len(s) # 初始值为1，表示只有该字符一种情况 dp = [1] * n # 每个字母最后一次出现的下标数组 last = [-1] * 26 for index, val in enumerate(s): for i in range(len(last)): # 只累加前方出现过，并且最后一次出现的下标 if last[i] != -1: dp[index] += dp[last[i]] % mod # 修改最后一次出现的下标 last[ord(s[index]) - ord('a')] = index ans = 0 # 累加结果 for i in range(26): if last[i] != -1: ans = (ans + dp[last[i]]) % mod return ans
