940.不同的子序列II

链接：940.不同的子序列II
难度：Hard
标签：字符串、动态规划
简介：给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

题解 1 - cpp

• 编辑时间：2022-10-14
• 执行用时：160ms
• 内存消耗：8.4MB
• 编程语言：cpp
• 解法介绍：动态规划，每个点记录当前值和遍历过的后个节点。

const int mod = 1e9 + 7;
struct Item {
    int val;
    bool next[26];
    Item(): val(0) {
        memset(next, 0, sizeof(bool) * 26);
    }
};
class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.size(), ans = 0;
        bool charList[26] = {0};
        vector<Item> dp(n);
        for (int i = 0; i < n; i++) {
            char c = s[i];
            if (charList[c - 'a'] == 0) dp[i].val += 1, charList[c - 'a'] = 1;
            for (int j = 0; j < i; j++) {
                if (dp[j].next[c - 'a']) continue;
                dp[j].next[c - 'a'] = true;
                dp[i].val = (dp[i].val + dp[j].val) % mod;
            }
            ans = (ans + dp[i].val) % mod;
        }
        return ans;
    }
};