Distinct Subsequences LeetCode solution in C++

1
class Solution {
2
 public:
3
  int solve(string &s, string &t, int i, int j, vector<vector<int>> &dp) {
4
    if (j >= t.size()) return 1;
5
    if (i >= s.size() || t.size() - j > s.size() - i) return 0;
6
    if (dp[i][j] != -1) return dp[i][j];
7
    int res = 0;
8
    for (int k = i; k < s.size(); k++) {
9
      if (s[k] == t[j]) res += solve(s, t, k + 1, j + 1, dp);
10
    }
11
    return dp[i][j] = res;
12
  }
13

14
  int numDistinct(string s, string t) {
15
    if (s.size() == t.size()) return s == t;
16
    vector<vector<int>> dp(s.size(), vector<int>(t.size(), -1));
17
    return solve(s, t, 0, 0, dp);
18
  }
19
};