115. 不同的子序列

题目链接：115. 不同的子序列 - 力扣（LeetCode）

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

解析：

简单dp，虽然题目说int范围内，但会中间值会越界，既然结果在int范围内，越界的直接mod int_max就好了

dp[n][m]表示s的n + 1个数是否可以从t的m + 1个数得到

当s[n] == t[m]的时候，dp[n][m] = dp[n - 1][m] + dp[n - 1][m - 1]

当s[n] != t[m]的时候，dp[n][m] = dp[n - 1][m]

class Solution {
public:int numDistinct(string s, string t) {int n = s.length();int m = t.length();int dp[1010][1010];memset(dp, 0, sizeof(dp));int mod = 2147483647;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i == 0 && j == 0) {if (s[i] == t[j]) dp[i][j] = 1;else dp[i][j] = 0;} else if (i < j) {dp[i][j] = 0;} else {if (s[i] == t[j]) {dp[i][j] = dp[i - 1][j];if (j == 0) dp[i][j] = (dp[i][j] + 1)  % mod;else dp[i][j] = ((long long)dp[i][j] + (long long)dp[i - 1][j - 1]) % mod;} else {dp[i][j] = dp[i - 1][j];}}}}return dp[n - 1][m - 1];}
};