目标
给定一个字符串 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 仅由小写英文字母组成
思路
返回字符串 s 不重复的非空子序列的个数。
定义 dp[i + 1][j] 表示 [0, i] 中以字母 j 结尾的子序列个数。使用当前字母作为子序列右端点的方案数为 1 + Σdp[i][j]，即 当前字母自身 加上 与之前的方案拼接。其它右端点的方案数与之前方案数相同 dp[i + 1][j] = dp[i][j]。
代码
/**
* @date 2026-09-08 14:54
*/
public class DistinctSubseqII940 {
public int distinctSubseqII(String s) {
int n = s.length();
int MOD = 1000000007;
int[][] dp = new int[n + 1][26];
for (int i = 0; i < n; i++) {
int sum = 0;
int c = s.charAt(i) - 'a';
for (int j = 0; j < 26; j++) {
dp[i + 1][j] = dp[i][j];
sum = (sum + dp[i][j]) % MOD;
}
dp[i + 1][c] = 1 + sum;
}
int res = 0;
for (int num : dp[n]) {
res = (res + num) % MOD;
}
return res;
}
}
性能
