115. Distinct Subsequences.md

115. Distinct Subsequences

• Method 1

  Use 2d dp. dp[i][j] stands for numbers of generation for first i of s and first j of t.

  Use long long and mod to avoid long long overflow.

  	Complexity
  Memory	O(mn)
  Time	O(mn)

  Solution:

  class Solution {
  public:
      int numDistinct(string s, string t) {
          long long m = s.length(), n = t.length();
          long long MOD = 3e9;
          vector<vector<long long>> dp(m, vector<long long>(n));
          for(long long i = 0; i < m; i++) {
              for(long long j = 0; j < min(i+1, n); j++) {
                  if(i) dp[i][j] = dp[i-1][j];
                  if(s[i] == t[j]) {
                      if(j) dp[i][j] += dp[i-1][j-1];
                      else dp[i][j] += 1;
                  } 
                  dp[i][j] %= MOD;
              }
          }
          long long ans = 0;
          return int(dp.back().back());
      }
  };