Leetcode392：

问题描述：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

代码思路解析：

假如只能使用动态规划法：

class Solution {
public://dp[i][j]代表s的前i个字符与t的前j个字符已经匹配字符的个数int dp[105][10005];bool isSubsequence(string s, string t) {int n1=s.size();int n2=t.size();for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(s[i-1]==t[j-1])dp[i][j]=1+dp[i-1][j-1];else dp[i][j]=dp[i][j-1];}}return dp[n1][n2]==n1;}
};

Leetcode115：

问题描述：

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

代码思路解析：

class Solution {
public://dp[i][j]表示，s前i个字符与t前j个字符已经匹配的子序列个数long long dp[1005][1005];int numDistinct(string s, string t) {int n=s.size();int m=t.size();if(n<m)return 0;for(int i=0;i<=n;i++){dp[i][0]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i-1]==t[j-1]){dp[i][j]= (dp[i-1][j-1]+dp[i-1][j])%(long long)(1e9+7);}elsedp[i][j]=dp[i-1][j]%(long long)(1e9+7);}}return dp[n][m];}
};