动态规划，求解《940. 不同的子序列 II》

var distinctSubseqII = function(s) {
  const n = s.length, lastIndexs = new Int16Array(26).fill(-1), dp = new Uint32Array(n).fill(1), MOD = 1e9 + 7
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < 26; j++) {
      if (lastIndexs[j] > -1) dp[i] = (dp[i] + dp[lastIndexs[j]]) % MOD
    }
    lastIndexs[s.charCodeAt(i) - 97] = i
  }
  let r = 0
  for (let j = 0; j < 26; j++) {
    if (lastIndexs[j] > -1) r = (r + dp[lastIndexs[j]]) % MOD
  }
  return r
};

function distinctSubseqII(s: string): number {
  const n = s.length, lastIds = new Int16Array(26).fill(-1), dp = new Uint32Array(n).fill(1)
  const MOD = 1e9 + 7
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < 26; j++) {
      if (lastIds[j] > -1) dp[i] = (dp[i] + dp[lastIds[j]]) % MOD
    }
    lastIds[s.charCodeAt(i) - 97] = i
  }
  let r = 0
  for (let j = 0; j < 26; j++) {
    if (lastIds[j] > -1) r = (r + dp[lastIds[j]]) % MOD
  }
  return r
};

define('MOD', 1e9 + 7);
class Solution {
  function distinctSubseqII($s) {
    $n = strlen($s);
    $dp = array_fill(0, $n, 1);
    $lastIs = array_fill(0, 26, -1);
    for ($i = 0; $i < $n; $i++) {
      for ($j = 0; $j < 26; $j++) {
        if ($lastIs[$j] > -1) $dp[$i] = ($dp[$i] + $dp[$lastIs[$j]]) % MOD;
      }
      $lastIs[ord($s[$i]) - 97] = $i;
    }
    $r = 0;
    for ($j = 0; $j < 26; $j++) {
      if ($lastIs[$j] > -1) $r = ($r + $dp[$lastIs[$j]]) % MOD;
    }
    return $r;
  }
}

func distinctSubseqII(s string) int {
   n, MOD := len(s), int(1e9 + 7)
   dp, lastIds := make([]int, n), make([]int, 26)
   for i := 0; i < n; i++ {
     dp[i] = 1
   }
   for j := 0; j < 26; j++ {
     lastIds[j] = -1
   }
   for i, c := range s {
     for j := 0; j < 26; j++ {
       if lastIds[j] > -1 {
         dp[i] = (dp[i] + dp[lastIds[j]]) % MOD
       }
     }
     lastIds[c - 'a'] = i
   }
   r := 0
   for j := 0; j < 26; j++ {
     if lastIds[j] > -1 {
       r = (r + dp[lastIds[j]]) % MOD
     }
   }
   return r
}

class Solution {
  public int distinctSubseqII(String s) {
    int n = s.length(), MOD = (int)1e9 + 7, r = 0;
    int[] dp = new int[n], lastIs = new int[26];
    for (int i = 0; i < n; i++) dp[i] = 1;
    for (int j = 0; j < 26; j++) lastIs[j] = -1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 26; j++) {
        if (lastIs[j] > -1) dp[i] = (dp[i] + dp[lastIs[j]]) % MOD;
      }
      lastIs[s.charAt(i) - 'a'] = i;
    }
    for (int j = 0; j < 26; j++) {
      if (lastIs[j] > -1) r = (r + dp[lastIs[j]]) % MOD;
    }
    return r;
  }
}

public class Solution {
  public int DistinctSubseqII(string s) {
    int n = s.Length, r = 0, MOD = (int)1e9 + 7;
    int[] dp = new int[n], lastIs = new int[26];
    for (int i = 0; i < n; i++) dp[i] = 1;
    for (int j = 0; j < 26; j++) lastIs[j] = -1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 26; j++) {
        if (lastIs[j] > -1) dp[i] = (dp[i] + dp[lastIs[j]]) % MOD;
      }
      lastIs[s[i] - 'a'] = i;
    }
    for (int j = 0; j < 26; j++) {
      if (lastIs[j] > -1) r = (r + dp[lastIs[j]]) % MOD;
    }
    return r;
  }
}

int distinctSubseqII(char * s){
  int n = strlen(s), MOD = 1e9 + 7, r = 0;
  int* dp = malloc(sizeof(int) * n);
  int* lastIs = malloc(sizeof(int) * 26);
  for (int i = 0; i < n; i++) dp[i] = 1;
  memset(lastIs, -1, sizeof(int) * 26); // memset 只能赋值 0 / -1
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      if (lastIs[j] > -1) dp[i] = (dp[i] + dp[lastIs[j]]) % MOD;
    }
    lastIs[s[i] - 'a'] = i; 
  }
  for (int j = 0; j < 26; j++) {
    if (lastIs[j] > -1) r = (r + dp[lastIs[j]]) % MOD;
  }
  return r;
}

class Solution {
public:
  int distinctSubseqII(string s) {
    int n = s.size(), MOD = 1e9 + 7, r = 0;
    vector<int> dp(n, 1), lastIs(26, -1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 26; j++) {
        if (lastIs[j] > -1) dp[i] = (dp[i] + dp[lastIs[j]]) % MOD;
      }
      lastIs[s[i] - 'a'] = i;
    }
    for (int j = 0; j < 26; j++) {
      if (lastIs[j] > -1) r = (r + dp[lastIs[j]]) % MOD;
    }
    return r;
  }
};

class Solution:
  def distinctSubseqII(self, s: str) -> int:
    n, r, MOD = len(s), 0, 1e9 + 7
    dp, lastIs = [1] * n, [-1] * 26
    for i in range(n):
      for j in range(26):
        if lastIs[j] > -1: dp[i] = (dp[i] + dp[lastIs[j]]) % MOD
      lastIs[ord(s[i]) - 97] = i
    for j in range(26):
      if lastIs[j] > -1: r = (r + dp[lastIs[j]]) % MOD
    return int(r)