不同序列dp

1987. 不同的好子序列数目

这题是周赛t4，跟下面那个一模一样。
只有一个不能以0开头是区别，这个还有点不太好想，单独去算如果含0就在答案+1

class Solution {
 public:
  int numberOfUniqueGoodSubsequences(string s) {
    int n = s.size();
    int f[n + 1][2];
    memset(f, 0, sizeof f);
    int zero = 0;
    const int MOD = 1e9 + 7;
    for (int i = 1; i <= n; i++) {
      if (s[i - 1] == '0') {
        f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
        f[i][1] = f[i - 1][1];
        zero = 1;
      } else {
        f[i][0] = f[i - 1][0];
        f[i][1] = (f[i - 1][0] + f[i - 1][1] + 1) % MOD;
      }
    }
    return (f[n][0] + f[n][1] + zero) % MOD;
  }
};

940. 不同的子序列 II

class Solution {
 public:
  int distinctSubseqII(string s) {
    int n = s.size();
    int f[n + 1][30];
    memset(f, 0, sizeof f);
    const int MOD = 1e9 + 7;
    for (int i = 1; i <= n; i++) {
      int sum = 0;
      for (char c = 'a'; c <= 'z'; c++) {
        if (s[i - 1] != c) f[i][c - 'a'] = f[i - 1][c - 'a'] % MOD;
        sum = (sum + f[i - 1][c - 'a']) % MOD;
      }
      f[i][s[i - 1] - 'a'] = (sum + 1) % MOD;
    }
    int res = 0;
    for (char c = 'a'; c <= 'z'; c++) res = (res + f[n][c - 'a']) % MOD;
    return res;
  }
};