目录
1. 题目引入：
2. 动态规划解法
2.1 动态dp表示
2.2 动态方程推导:
2.3 具体分析
2.4 初始化
3. 代码如下
java版
c++版
Python版
1. 题目引入：
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"输出：3解释： 如下所示, 有 3 种可以从 s 中得到"rabbit" 的方案。rabbbitrabbbitrabbbit
示例 2：
输入：s = "babgbag", t = "bag"输出：5解释： 如下所示, 有 5 种可以从 s 中得到"bag" 的方案。babgbagbabgbagbabgbagbabgbagbabgbag
提示：
1 <= s.length, t.length <= 1000s和t由英文字母组成
2. 动态规划解法
2.1 动态dp表示
dp[i][j] 代表 t 前 i 字符串可以由 s j 字符串组成最多个数.
2.2 动态方程推导:
当 s[j] == t[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
当 s[j] != t[i] , dp[i][j] = dp[i][j-1]
2.3 具体分析
很多朋友们拿到这种dp数组的题，知道要用动态规划，但是往往有时不知道如何写动态转移方程和初始化赋值。我觉得有两种思考方法，
--------第一，可以画出dp的数组，自己从中找出规律，然后考虑边界值以及初始化赋值（常用）。
例如：
s = "babgbag", t = "bag"
- ~~~ 可以先画出来dp的样子，一般对于字符串的动态规划的题，都是定义dp[i][j]为s为i,t为j时所求问题的子问题的答案，这里先不具体分析初始条件。以先找规律为主。由于字符比较简单，可以自己很快就把这个dp数组填满。
- ~~~可以发现这个规律
当 S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
当 S[j] != T[i] , dp[i][j] = dp[i][j-1]
当然了，一下子写出这个答案对于刚入门动态规划的朋友来说是有点不能接受的。所以可以参考第二种方法 。
--------第二，直接观察题目所给的字符串，从第一个字符或者最后一个字符来分析。解决最简单的一个问题，然后递推到子问题。有点像递归的分析。其实dp就像是从字问题推到最终问题的递归版本的解法。
还是以s = "babgbag", t = "bag"为例
先假设前面的dp已经推导出来了。
- 当最后s,t一个元素相同时:
对于s = "babgba", t = "ba"。我们试图用s="babgba"的子序列来表示t="ba"。这里我们可以两种选择方法
选取s = "babgba"来表示t="ba",我们选择s = "babgba"的字符a来表示，此为情况一。
既然我们确定了要选a，就可以只看dp[i-1][j-1]了。就相当于s = "babgba"的a与t="ba"抵消掉了。因为这个两个字符串（s，t）末尾的a是固定的，并不会改变他们各自的前一个状态。
选取s = "babgb"来表示t="ba",我们不选择s = "babgba"的字符a来表示，此为情况二。
问题可以简化为看dp[i][j-1]。具体理解可参考下图
如图我们可以这样选择：
2.4 初始化
j==0时，dp[i][0] = 1i==0时，dp[0][j] = 0
如图举例所示 ‘’为空字符串，即当s为‘’时只能表示‘’，故dp[0][0]=1,s为‘’，其余不为‘’则初始化为0
希望读者可以理解这里为什么是dp[i][j-1],dp[i-1][j-1].如果实在不理解可以对照着表格来写一遍。
3. 代码如下
java版
class Solution {public int numDistinct(String s, String t) {int n1 = s.length();int n2 = t.length();int[][] dp = new int[n2 + 1][n1 + 1];for (int j = 0; j <= n1; j++) {dp[0][j] = 1;}for (int i = 1; i <= n2; i++) {for (int j = 1; j <= n1; j++) {if (t.charAt(i - 1) == s.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];} else {dp[i][j] = dp[i][j - 1];}}}return dp[n2][n1];}
}
c++版
#include <iostream>
#include <vector>using namespace std;int numDistinct(string s, string t) {int n1 = s.size();int n2 = t.size();vector<vector<int>> dp(n2 + 1, vector<int>(n1 + 1, 0));for (int j = 0; j <= n1; j++) {dp[0][j] = 1;}for (int i = 1; i <= n2; i++) {for (int j = 1; j <= n1; j++) {if (t[i - 1] == s[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];} else {dp[i][j] = dp[i][j - 1];}}}return dp[n2][n1];
}Python版
class Solution:def numDistinct(self, s: str, t: str) -> int:n1 = len(s)n2 = len(t)dp = [[0] * (n1 + 1) for _ in range(n2 + 1)]for j in range(n1 + 1):dp[0][j] = 1for i in range(1, n2 + 1):for j in range(1, n1 + 1):if t[i - 1] == s[j - 1]:dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]else:dp[i][j] = dp[i][j - 1]#print(dp)return dp[-1][-1]此为初学dp期间的学习与思考，如有不恰当表述之处，欢迎大佬指正！
